DP table

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.

Exercise LCS length DP

Write lcs_len(s1, s2). Find LCS length with a DP table. Print 4 with print(lcs_len("ABCBDAB", "BDCAB")).

Show example 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"))

Test yourself

Match recurrence

dp[i][j] = dp[i - 1][j - 1] + ____

Show answer

dp[i][j] = dp[i - 1][j - 1] + 1

DP table: match the terms

dp[i][j]

Cell
match

Match
diagonal

Diagonal
max

Max
What size is the LCS table?
- (m+1) × (n+1)
- (m-1) × (n-1)
- m + n
- m × n
Show answer

(m+1) × (n+1) — (m+1) × (n+1).

Next lesson: Backtracking the table

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies