This method checks for every subsequence of sequence S1 whether it also appears in sequence S2. S1 and S2 are two sequences with n and m lengths, respectively. LCS( S1[1…m-1],S2[1….n]),LCS(S1[1…m],S2[1…..n-1])).

It allows us to compute a problem, store the optimal solution, and then reuse it to avoid repeated executions. DP[i][j] state: Longest sequence using starting i characters in S1 and starting j characters in S2.