Skip to content
Laviyx Learn

Try

DSA course menu

2D Dynamic Programming: Grid Paths, LCS and Edit Distance

Solve two-dimensional dynamic programming problems in Python: unique paths in a grid, minimum path sum, longest common subsequence, edit distance (Levenshtein), and rebuilding the answer from the table.

Advanced9 min readUpdated
On this page

In two-dimensional DP, the state needs two numbers: a cell in a grid (row, col), or positions in two strings (i, j). The table is a grid, and each cell is computed from cells above and to the left of it, so it is filled row by row.

Unique paths in a grid#

A robot starts in the top-left corner of an m × n grid and can only move right or down. How many paths reach the bottom-right?

  • State: dp[r][c] = number of paths to cell (r, c).
  • Recurrence: a cell is reached from above or from the left: dp[r][c] = dp[r-1][c] + dp[r][c-1].
  • Base: the first row and first column each have exactly 1 path.
Python
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    for row in dp:
        print(row)
    return dp[m - 1][n - 1]

print(unique_paths(3, 4))
Output
[1, 1, 1, 1]
[1, 2, 3, 4]
[1, 3, 6, 10]
10

Minimum path sum#

Each cell has a cost. Find the cheapest path from the top-left to the bottom-right, moving right or down. Same shape, with min instead of +:

Python
def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                dp[r][c] = grid[0][0]
            elif r == 0:
                dp[r][c] = dp[r][c - 1] + grid[r][c]
            elif c == 0:
                dp[r][c] = dp[r - 1][c] + grid[r][c]
            else:
                dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c]
    return dp[-1][-1]

grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
]
print(min_path_sum(grid))
Output
7

The cheapest route is 1 → 3 → 1 → 1 → 1 = 7.

Longest common subsequence (LCS)#

Find the longest sequence of characters that appears, in order, in both strings (not necessarily contiguously). LCS is behind diff tools that compare files.

  • State: dp[i][j] = LCS length of the first i characters of a and the first j characters of b.
  • Recurrence: if a[i-1] == b[j-1], extend: dp[i-1][j-1] + 1. Otherwise drop a character from one string: max(dp[i-1][j], dp[i][j-1]).
Python
def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # walk back through the table to rebuild one LCS
    i, j, chars = len(a), len(b), []
    while i and j:
        if a[i - 1] == b[j - 1]:
            chars.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[len(a)][len(b)], "".join(reversed(chars))

print(lcs("ABCBDAB", "BDCABA"))
print(lcs("programming", "gaming"))
Output
(4, 'BCBA')
(6, 'gaming')

The extra row and column of zeros represent empty prefixes, so no special base cases are needed. Time and space are O(m × n).

Edit distance#

The fewest single-character insertions, deletions or replacements to turn one word into another (also called Levenshtein distance). Spell checkers and DNA comparison use it.

  • State: dp[i][j] = edit distance between the first i characters of a and the first j of b.
  • Base: turning a prefix into the empty string takes i deletions; building a prefix from empty takes j insertions.
  • Recurrence: if the last characters match, dp[i-1][j-1]. Otherwise 1 + the cheapest of delete (dp[i-1][j]), insert (dp[i][j-1]) or replace (dp[i-1][j-1]).
Python
def edit_distance(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete
                                   dp[i][j - 1],      # insert
                                   dp[i - 1][j - 1])  # replace
    return dp[len(a)][len(b)]

print(edit_distance("kitten", "sitting"))
print(edit_distance("horse", "ros"))
print(edit_distance("", "abc"))
Output
3
3
3

kitten → sitten (replace k) → sittin (replace e) → sitting (insert g): 3 edits.

Saving space#

Each row only uses the row above it, so two rows of length n are enough, cutting space from O(m × n) to O(n). The cost is that you can no longer walk back through the table to rebuild the actual sequence, as lcs did.

Common mistakes#

Practice#

Practice exercise

Write longest_palindromic_subsequence(s), the length of the longest subsequence of s that reads the same both ways.

Show hint

A palindrome read backwards is itself, so the answer is the LCS of s and s[::-1].

Show solution
Python
def lcs_length(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[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[-1][-1]

def longest_palindromic_subsequence(s):
    return lcs_length(s, s[::-1])

print(longest_palindromic_subsequence("bbbab"))
print(longest_palindromic_subsequence("character"))
Output
4
5

"bbbb" (length 4) is hidden in "bbbab", and "carac" (length 5) in "character".

Key takeaway#

Next: choosing items under a limit, in The Knapsack Problem.

Finished this lesson?

Related lessons

DSADynamic Programming for Beginners: Memoization and TabulationLearn dynamic programming step by step: overlapping subproblems and optimal substructure, top-down memoization, bottom-up tabulation, space optimisation, and a five-step method for solving DP problems.Advanced7 min readDSA1D Dynamic Programming Problems: House Robber, Coin Change and LISSolve classic one-dimensional dynamic programming problems in Python: house robber, minimum cost climbing stairs, coin change, number of ways to make change, decode ways, maximum subarray (Kadane) and longest increasing subsequence.Advanced10 min readDSAThe Knapsack Problem: 0/1 and Unbounded Knapsack in PythonLearn the 0/1 knapsack problem with dynamic programming: the DP table, choosing items, the one-row space optimisation, unbounded knapsack, subset sum and partition problems, and fractional knapsack with greedy.Advanced10 min readDSAStrings in DSA: Immutability, Building Strings and Classic ProblemsStrings for data structures and algorithms in Python: why strings are immutable, the O(n²) concatenation trap, using join, character counting, palindromes and anagrams.Beginner6 min read

Recommended DSA resources

Some links are affiliate links. If you buy through them, Laviyx Learn may earn a commission at no extra cost to you. As an Amazon Associate, we earn from qualifying purchases.