DP table
- Algorithms course
- Advanced
- Lesson 10/56
- 4 min
Build a 2D DP table for LCS.
DP table
We build a 2D DP table for LCS. dp[i][j] is the LCS length of s1's first i and s2's first j characters.
The table is (len(s1)+1) × (len(s2)+1); the first row and column are zero.
Each cell is filled as diagonal+1 if chars match, else max of left/top.
Cell recurrence
If s1[i-1] == s2[j-1] then dp[i][j] = dp[i-1][j-1] + 1. Else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
This recurrence, by filling the table in order, gives the LCS length.
The result is in dp[len(s1)][len(s2)]; the bottom-right corner of the table.
Practice LCS length DP
Write lcs_len(s1, s2). Find LCS length with a DP table. Print 4 with print(lcs_len("ABCBDAB", "BDCAB")).
Starter code
def lcs_len(s1, s2):
# LCS length DPSample solution
def lcs_len(s1, s2):
# LCS length DP
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
print(lcs_len("ABCBDAB", "BDCAB"))Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Match recurrence
dp[i][j] = dp[i - 1][j - 1] + ____dp[i][j] = dp[i - 1][j - 1] + 1Explanation: 1 is right.
2 DP table: match the terms
| Term | Meaning |
|---|---|
dp[i][j] |
Cell |
match |
Match |
diagonal |
Diagonal |
max |
Max |
3 What size is the LCS table?
- (m+1) × (n+1) Correct answer
- (m-1) × (n-1)
- m + n
- m × n
Explanation: (m+1) × (n+1).