LeetCode 1143 Longest Common Subsequence - Solution

The core idea

Define dp[i][j] = LCS length for first i chars of text1 and first j chars of text2.

If text1[i-1] == text2[j-1]: characters match, extend by 1. dp[i][j] = dp[i-1][j-1] + 1.

Otherwise: take the best we can get without one of the characters. dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Base: dp[0][j] = dp[i][0] = 0. Answer: dp[m][n].