حل تشریحی سوال شماره 2 ساختمان داده

می خواهیم بزرگ ترین زیر دنباله مشترک دو دنباله $a_1,\dots ,a_n$ و $b_1,\dots ,b_m$ را محاسبه کنیم. فرض کنید L(i,j) برابر طول بزرگترین زیر دنباله مشترک $a_1,\dots ,a_n$ و $b_1,\dots ,b_m$ باشد. کدام یک از تعاریف بازگشتی زیر درست است؟

الف) $L\left(n,m\right)=\max \left(L\left(n-1,m\right)\right),L\left(n,m-1\right),L\left(n-1,m-1+1if{a}_n=b_m\right)$

ب) $L\left(n,m\right)=\max \left(L\left(n-1,m\right),L\left(n-1,k-1\right)+1\right)$ که K برابر بزرگ‌ترین عددی است که $a_n=b_k$ (در صورت عدم وجود خواهد بود)

فرض کنید $L\left(i,0\right)=L\left(0,i\right)=0$ و $L\left(i,-1\right)=-1$ برای هر $i\ge 0$