$(10\%)$ Given two strings $A=a_1{a}_{2}dots{a}_m$ and $B=b_1{b}_{2}dots{b}_n,$ the longest common subsequence

$($LCS$)$ problem is to find a longest common subsequence between A and $B.$ Please design a

dynamic program algorithm to solve the $LCS$ problem $(3\%).$ What is the recursive formula for

your dynamic programming algorithm $(3\%)?$ Note that you have to justify the correctness of

your recursive formula. Also analyze the time complexity of your dynamic programming

algorithm $(4\%).$