Two-dimensional DP appears whenever the state needs two positions, for example one index into each of two strings. dp[i][j] then means "the answer for the first i characters of one string and the first j of the other".
Given two strings text1 and text2, return the length of their longest common subsequence (characters taken in order, not necessarily contiguous). If there is none, return 0.
Examples
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: "ace"
Input: text1 = "abc", text2 = "def"
Output: 0
Constraints
0 <= len(text1), len(text2) <= 500, lowercase letters only- Target: O(len(text1) * len(text2)) time
Goals
- Set up a 2D DP table indexed by prefixes of two strings
- Derive the match / no-match recurrence
- Pad the table with an extra row and column so base cases need no special handling