Dynamic Programming II: Two Dimensions, Strings and Knapsack

When a problem has two changing quantities, such as positions in two strings, a position and a remaining budget, or a row and a column, the DP state needs two indexes, and the table is two-dimensional. The four-step method from the previous chapter is unchanged: define the state in words, write the transition, set the base cases, and decide the order. This chapter applies it to grids, string comparison, the knapsack family and a few interval-style problems.

1. Recognising a two-dimensional state

Ask: "What do I need to know to describe where I am in the problem?"

• Two sequences (compare two strings): the pair (i, j) of positions in each.
• A grid: the cell (row, col).
• Choosing items under a budget: (item index, remaining capacity).
• A range of an array: (left, right).
• A sequence with a limited resource: (position, how many used).

If one index is not enough to make the future independent of the past, add another.

2. Grid paths

Unique paths. Count the paths from the top-left to the bottom-right of an $m\times n$ grid, moving only right or down.

• State: dp[r][c] = the number of ways to reach cell (r, c).
• Transition: dp[r][c] = dp[r-1][c] + dp[r][c-1].
• Base: the first row and first column each have exactly one path.

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]
    return dp[m - 1][n - 1]

assert unique_paths(3, 7) == 28
assert unique_paths(3, 2) == 3
assert unique_paths(1, 1) == 1

Space optimisation. Row r depends only on row r - 1, so keep a single row and update it in place.

def unique_paths_1d(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]          # row[c] (old) is the cell above, row[c-1] (new) is the cell to the left
    return row[-1]

assert unique_paths_1d(3, 7) == 28

Minimum path sum. Minimise the sum of values along a path. The transition becomes grid[r][c] + min(up, left).

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

assert min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) == 7
assert min_path_sum([[1, 2, 3], [4, 5, 6]]) == 12

Unique paths with obstacles sets dp to 0 for blocked cells. Maximal square uses dp[r][c] = 1 + min(up, left, diagonal) when the cell is 1: the side length of the largest square whose bottom-right corner is here.

def maximal_square(matrix):
    if not matrix:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]      # a padded border avoids edge cases
    best = 0
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            if matrix[r - 1][c - 1] == "1":
                dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
                best = max(best, dp[r][c])
    return best * best

assert maximal_square([list("10100"), list("10111"), list("11111"), list("10010")]) == 4
assert maximal_square([list("0")]) == 0

3. Longest common subsequence

Given two strings, find the length of the longest sequence of characters that appears in both in the same order (not necessarily contiguously).

• State: dp[i][j] = the LCS length of the first i characters of a and the first j characters of b.
• Transition: if a[i-1] == b[j-1], the characters match and extend the best of the smaller problem: dp[i][j] = dp[i-1][j-1] + 1. Otherwise, drop one character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
• Base: dp[0][*] = dp[*][0] = 0.

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

assert lcs_length("abcde", "ace") == 3
assert lcs_length("abc", "abc") == 3
assert lcs_length("abc", "def") == 0
assert lcs_length("", "abc") == 0

Time and space $O(mn)$. Since row i depends only on row i - 1, space can drop to $O(\min (m,n))$ if you only need the length. To recover the subsequence itself, keep the full table and walk back from dp[m][n]: if the characters match, take the character and move diagonally, else move toward the larger neighbour.

def lcs_string(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i - 1][j - 1] + 1 if a[i - 1] == b[j - 1] else max(dp[i - 1][j], dp[i][j - 1])
    out, i, j = [], m, n
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

assert lcs_string("abcde", "ace") == "ace"
assert len(lcs_string("AGGTAB", "GXTXAYB")) == 4

LCS underlies many variants: longest palindromic subsequence is the LCS of a string and its reverse, minimum insertions to make a palindrome follows from it, and shortest common supersequence and diff tools use it too.

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

assert longest_palindromic_subsequence("bbbab") == 4
assert longest_palindromic_subsequence("cbbd") == 2

4. Edit distance

The minimum number of single-character edits (insert, delete, replace) to turn one string into another.

• State: dp[i][j] = the edit distance between the first i characters of a and the first j of b.
• Transition: if the characters match, no cost: dp[i-1][j-1]. Otherwise 1 + min( replace dp[i-1][j-1], delete dp[i-1][j], insert dp[i][j-1] ).
• Base: dp[i][0] = i (delete everything), dp[0][j] = j (insert everything).

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 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 - 1], dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

assert edit_distance("horse", "ros") == 3
assert edit_distance("intention", "execution") == 5
assert edit_distance("", "abc") == 3
assert edit_distance("same", "same") == 0

Be ready to explain the three operations in terms of the table: moving diagonally is a match or replace, moving up is a delete from a, moving left is an insert into a.

5. The knapsack family

0/1 knapsack. Given items with weights and values and a capacity, choose items (each at most once) to maximise value without exceeding capacity.

• State: dp[i][w] = the best value using the first i items with capacity w.
• Transition: skip item i (dp[i-1][w]), or take it if it fits (dp[i-1][w - weight] + value).

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                                   # skip
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])   # take
    return dp[n][capacity]

assert knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9
assert knapsack([2, 3], [3, 4], 1) == 0

Time $O(n\cdot W)$, called pseudo-polynomial, because it depends on the numeric value of the capacity, not just the input length. Mention that nuance.

Space optimisation to one row. Iterate capacity downward so each item is used at most once (the cell w - weight has not yet been updated for this item).

def knapsack_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):          # downward: 0/1, each item once
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]

assert knapsack_1d([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9

Iterating upward instead would let an item be reused, which is the unbounded knapsack, as in coin change. The direction of the loop is exactly the 0/1 versus unbounded distinction. Know that cold.

Partition equal subset sum. Can the array be split into two subsets with equal sum? That is a subset-sum question: is there a subset summing to total / 2? A boolean 0/1 knapsack.

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target                    # dp[s] = some subset sums to s
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

assert can_partition([1, 5, 11, 5]) is True
assert can_partition([1, 2, 3, 5]) is False
assert can_partition([2, 2]) is True

Target sum (assign + or - to each number to reach a target) reduces to subset sum: if P is the sum of the positive group, then P = (total + target) / 2.

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0
    goal = (total + target) // 2
    dp = [1] + [0] * goal                              # number of subsets that sum to each value
    for x in nums:
        for s in range(goal, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[goal]

assert find_target_sum_ways([1, 1, 1, 1, 1], 3) == 5
assert find_target_sum_ways([1], 1) == 1
assert find_target_sum_ways([1], 2) == 0

The recurring skill is reduction: transform the story into a known DP (subset sum, knapsack, LCS).

6. Longest palindromic substring

Find the longest contiguous palindrome. The $O(n^2)$ DP table dp[i][j] (is s[i..j] a palindrome?) works, and the simpler expand around centre approach is $O(n^2)$ time and $O(1)$ space: every palindrome has a centre (a character, or a gap between two), so try each centre and grow outward.

def longest_palindrome(s):
    best = ""
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    for i in range(len(s)):
        for candidate in (expand(i, i), expand(i, i + 1)):       # odd and even length
            if len(candidate) > len(best):
                best = candidate
    return best

assert longest_palindrome("babad") in ("bab", "aba")
assert longest_palindrome("cbbd") == "bb"
assert longest_palindrome("a") == "a"

Mention Manacher's algorithm as an $O(n)$ method without implementing it.

7. Interval DP and decision DP

Interval DP has states over ranges (i, j), solved by increasing range length. Typical problems: burst balloons, matrix chain multiplication, palindrome partitioning cost. The pattern: dp[i][j] depends on splitting the range at some point k and combining dp[i][k] and dp[k][j].

def min_cost_to_cut_stick_like(nums):
    """Burst balloons: max coins from bursting all balloons; the last balloon burst in (i, j) is k."""
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):                       # range length, from small to large
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):                # k is the LAST balloon burst between i and j
                dp[i][j] = max(dp[i][j], dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j])
    return dp[0][n - 1]

assert min_cost_to_cut_stick_like([3, 1, 5, 8]) == 167
assert min_cost_to_cut_stick_like([1, 5]) == 10

The trick, choosing the last action in a range rather than the first, is characteristic of interval DP, and one to remember.

Stock problems add a state of holding or not and a transaction count. For example, with a cooldown after selling:

def max_profit_with_cooldown(prices):
    hold, sold, rest = float("-inf"), 0, 0
    for p in prices:
        prev_sold = sold
        sold = hold + p                     # sell today
        hold = max(hold, rest - p)          # keep holding, or buy today (after resting)
        rest = max(rest, prev_sold)         # do nothing today
    return max(sold, rest)

assert max_profit_with_cooldown([1, 2, 3, 0, 2]) == 3
assert max_profit_with_cooldown([1]) == 0

Modelling a process as a small state machine (hold, sold, rest) and writing a transition for each state is a powerful template.

8. A checklist for any DP problem

1. Brute force recursion first. What are the choices at each step? Can you write f(state)?
2. What is the minimum information you need to continue from a state? That defines the state. Fewer variables mean a smaller table.
3. Write the recurrence and the base cases.
4. Memoise, then tabulate if you want.
5. State the complexity: number of states times the work per state.
6. Optimise space by noticing which previous rows or values are needed.
7. Reconstruct the answer if the problem asks for the actual solution: store choices or walk the table back.

9. Common mistakes

• Wrong loop direction in knapsack, turning 0/1 into unbounded or the reverse.
• Mixing up the indexes of dp (which has an extra row and column) and the strings or arrays (0-indexed).
• Reading dp[i - 1][j - 1] when i or j is 0 without a padded border.
• Initialising dp with the wrong sentinel (0 versus infinity versus negative infinity).
• Overwriting values that are still needed when compressing space.
• Too big a state, such as tracking the whole subset, when a number would do.
• Not seeing the reduction from a story to a known DP.
• Giving the time complexity as just $O(n^2)$ when it is $O(nm)$, or forgetting that a substring comparison inside the loop adds a factor.

10. Practice set

1. Unique paths I and II, minimum path sum, triangle, maximal square.
2. Longest common subsequence, longest palindromic subsequence, shortest common supersequence.
3. Edit distance, distinct subsequences, interleaving string.
4. 0/1 knapsack, partition equal subset sum, target sum, last stone weight II.
5. Coin change II, combination sum IV (permutations), perfect squares.
6. Longest palindromic substring, palindromic substrings count.
7. Best time to buy and sell stock III and IV, with cooldown, with fee.
8. Burst balloons, minimum cost to merge stones, matrix chain multiplication.
9. Regular expression matching, wildcard matching.
10. Dungeon game (DP from the end), cherry pickup, and a bitmask DP such as the travelling salesman on $n\le 15$.