Compute the length of longest common subsequence for the two input strings x $=$ ABCBDAB and y $=$ BDCABA using the dynamic programming algorithm$($see the attached photo$).$show your work by filling the DP table.Solution $1.$ Dynamic programming.

Def. OPT$(i,j)=$ length of LCS of prefix strings $x_1{x}_{2}dots{x}_i$ and $y_1{y}_{2}dots{y}_j.$

Goal. OPT$(m,n).$

Case $1.x_i=y_j.$

$1+$ length of LCS of $x_1{x}_{2}dots{x}_{i-1}$ and $y_1{y}_{2}dots{y}_{j-1}.$

optimal substructure property

$($proof via exchange argument$)$

Case $2.x_i{y}_j.$

Delete $x_i$ : length of LCS of $x_1{x}_{2}dots{x}_{i-1}$ and $y_1{y}_{2}dots{y}_j.$

Delete $y_j$ : length of LCS of $x_1{x}_{2}dots{x}_i$ and $y_1{y}_{2}dots{y}_{j-1}.$

Bellman equation.

OPT$(i,j)=\{\begin{array}{ccc}0& ifi=0or& j=0\\ 1+\text{O}\text{P}\text{T}& (i-1,j-1)if& x_i=y_j\\ \text{m}\text{a}\text{x}& \{OPT(i-1,j),\text{O}\text{P}\text{T}(i,j-1)\}if& x_i{y}_j\end{array}$