2D DP

Build 2D DP tables for longest common subsequence, edit distance, and unique paths in a grid.

When a problem involves two sequences or a grid, the sub-problem state needs two dimensions: dp[i][j] encodes the answer for the first i characters of one input and the first j of another (or row i, column j of a grid).

Three 2D DP problems

Python — editable, runs in your browser

# ── 1. Longest Common Subsequence ───────────────────────────────────────────
# lcs(s1, s2): length of the longest subsequence present in both strings.
# A subsequence need not be contiguous.

def lcs(s1, s2):
  m, n = len(s1), len(s2)
  # dp[i][j] = LCS length of s1[:i] and s2[:j]
  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]

# ── 2. Edit Distance (Levenshtein) ───────────────────────────────────────────
# Minimum single-character edits (insert, delete, replace) to turn s1 into s2.

def edit_distance(s1, s2):
  m, n = len(s1), len(s2)
  dp = [[0] * (n + 1) for _ in range(m + 1)]
  for i in range(m + 1):
      dp[i][0] = i          # delete all chars in s1[:i]
  for j in range(n + 1):
      dp[0][j] = j          # insert all chars of s2[:j]
  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]   # chars match — no cost
          else:
              dp[i][j] = 1 + min(
                  dp[i - 1][j],     # delete from s1
                  dp[i][j - 1],     # insert into s1
                  dp[i - 1][j - 1], # replace
              )
  return dp[m][n]

# ── 3. Unique Paths ──────────────────────────────────────────────────────────
# In an m x n grid, start at top-left, reach bottom-right.
# Only move right or down. Count distinct paths.

def unique_paths(m, n):
  dp = [[1] * n for _ in range(m)]  # first row and col are all 1
  for i in range(1, m):
      for j in range(1, n):
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  return dp[m - 1][n - 1]

# ── Demo ─────────────────────────────────────────────────────────────────────
print("LCS")
print(lcs("ABCBDAB", "BDCABA"))   # 4  (e.g. BCBA or BDAB)
print(lcs("AGGTAB", "GXTXAYB"))   # 4  (GTAB)

print()
print("Edit distance")
print(edit_distance("kitten", "sitting"))  # 3
print(edit_distance("sunday", "saturday")) # 3
print(edit_distance("", "abc"))            # 3
print(edit_distance("abc", "abc"))         # 0

print()
print("Unique paths")
print(unique_paths(3, 7))   # 28
print(unique_paths(3, 2))   # 3
print(unique_paths(1, 1))   # 1

LCS: the diagonal trick

dp[i][j] compares s1[i-1] and s2[j-1]:

Characters match: extend the LCS of the shorter prefixes: dp[i-1][j-1] + 1.
Characters differ: the LCS is the best of "ignore the last char of s1" or "ignore the last char of s2": max(dp[i-1][j], dp[i][j-1]).

The table for lcs("ABCD", "ACBD") (LCS = 3):

    ""  A  C  B  D
""   0  0  0  0  0
A    0  1  1  1  1
B    0  1  1  2  2
C    0  1  2  2  2
D    0  1  2  2  3

The answer is always in the bottom-right cell.

Edit distance: three operations at each cell

At each dp[i][j], three operations are available to transform s1[:i] into s2[:j]:

Delete s1[i-1]: cost = dp[i-1][j] + 1
Insert s2[j-1]: cost = dp[i][j-1] + 1
Replace (if characters differ): cost = dp[i-1][j-1] + 1

The base cases initialise the first row and column: transforming an empty string into length-j costs j insertions; transforming length-i into empty costs i deletions.

Edit distance is the engine behind spell-checkers, diff tools, and DNA sequence alignment. In practice, the full table is often not needed — you only keep two rows at a time for O(min(m,n)) space.

Unique paths: simple grid DP

Every cell can only be reached from above or from the left, so the recurrence is just dp[i][j] = dp[i-1][j] + dp[i][j-1]. The first row and first column are all 1 because there is only one way to reach any cell along the edges (always move in the same direction).

Where to go next

Next: lab — DP problems — three guided exercises: word break, house robber, and longest increasing subsequence.

Finished reading? Mark it complete to track your progress.

Three 2D DP problems

LCS: the diagonal trick

Edit distance: three operations at each cell

Unique paths: simple grid DP

Where to go next

On this page