Longest Common Subsequence
Now, we will look through how to solve a popular dynamic programming problem, LCS or longest common subsequence problem. Problem Statement : Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. Example : LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4. Solution : First of all lets see how to approach the problem and see how this problem qualifies to be a DP problem. 1) Optimal Substructure: Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the leng