DP Patterns, Part 2: Grids, Intervals, Bitmasks and Trees

You can already fill a table for coin change or edit distance. The hard part of a new problem is not the filling. It is deciding what one cell should mean. This lesson gives you a method for that decision, then uses it on five shapes that cover most of what interviews and real systems throw at you: grids, increasing sequences, intervals, small sets and trees.

Learning Objectives

After this lesson, you will be able to:

Design a dynamic program from a blank page with five questions: state, transition, base case, order and answer
Solve grid problems (unique paths, with obstacles, minimum path sum) and say why the fill order is safe
Explain why the tails list gives the longest increasing subsequence in O(n log n), and when to use bisect_left or bisect_right
Fill an interval table by increasing length for burst balloons and palindrome cuts, and state the O(n³) cost
Use a whole number as a set of visited items (a bitmask) to solve a small travelling salesman, and say when it stops being possible
Shrink a table to one row, rebuild the actual answer and not just its value, and choose between DP, greedy, backtracking and plain recursion

Prerequisites

Before You Start

Review

#Quick Recap: What Part 2 Taught

Five lines are enough. If any feels shaky, open the linked lesson first.

Dynamic programming (DP) solves a big problem from the answers to smaller versions of itself, and each small answer is stored so it is computed only once (Recursion and DP).
Memoization is top-down: write the recursion and cache each result by its arguments.
Tabulation is bottom-up: fill a table in an order where every cell's inputs are already there.
The classics (coin change, knapsack, longest common subsequence, edit distance) are one technique used four times (Part 2).
A table of m by n cells costs O(m * n) time, and keeping only the rows you still need can cut the space.

#The Design Method: Five Questions

When a DP problem looks new, do not hunt for a trick. Answer five questions, in this order.

State. What does one cell of the table mean? Write it as a sentence, such as "best[i] is the most money from the first i houses".
Transition. How is one cell built from smaller cells? This is the recurrence, and it is nearly always a min, a max or a sum over a few choices.
Base case. Which cells have an answer you know without computing, such as the empty prefix?
Order. In what order can you fill the cells so each one's inputs are ready?
Answer. Which cell holds what the question asked for?

A good state has one property: two different histories that land in the same state have the same future. That is why a cache works. If the state forgets something the future needs, the answers are wrong. If it remembers too much, the table is huge.

Take a worked example. A street has houses in a row, and house i holds money[i]. You may not rob two neighbouring houses. What is the most you can take? Here are the answers to the five questions.

State: best[i] is the most money from the first i houses.
Transition: either skip house i and keep best[i-1], or rob it and add best[i-2], because the neighbour is off limits.
Base case: best[0] = 0, since no houses means no money.
Order: left to right.
Answer: best[n].

Trace it by hand for [2, 7, 9, 3, 1] before reading any code. One row is one house.

i	money	skip: best[i-1]	rob: money + best[i-2]	best[i]
1	2	0	2 + 0 = 2	2
2	7	2	7 + 0 = 7	7
3	9	7	9 + 2 = 11	11
4	3	11	3 + 7 = 10	11
5	1	11	1 + 11 = 12	12

The answer is the last cell. Notice row 4: robbing house 4 would give 10, skipping gives 11, so the best stays 11.

pythonrunnable cell

def rob(money):
    n = len(money)
    best = [0] * (n + 1)                   # best[0] = 0 is the base case
    for i in range(1, n + 1):
        take = money[i - 1] + (best[i - 2] if i >= 2 else 0)
        best[i] = max(best[i - 1], take)   # skip the house, or rob it
    return best


print(rob([2, 7, 9, 3, 1]))
print(rob([5]), rob([]))
# Output:
# [0, 2, 7, 11, 11, 12]
# [0, 5] [0]

The time is O(n), one step per cell, and the space is O(n) for the table. Keep this recipe. Every section below is the same five questions with a different state.

#Grid DP: Unique Paths, Obstacles and Minimum Path Sum

A grid DP has a cell for each square of a grid, and a cell is built from the cell above it and the cell to its left. Start with a prediction.

What Do You Think?

A robot stands in the top-left square of a 3 by 3 grid. It may move only right or down. It must reach the bottom-right square. How many different routes are there?

Now the five questions. State: dp[r][c] is the number of routes from the top-left to square (r, c). Transition: you arrive from above or from the left, so dp[r][c] = dp[r-1][c] + dp[r][c-1]. Base case: the start has 1 route, and a square outside the grid adds 0. Order: row by row, left to right, so above and left are always filled. Answer: the bottom-right cell.

Fill a 3 by 3 grid by hand. The first row and first column are all 1, because there is only one way along an edge.

	col 0	col 1	col 2
row 0	1	1	1
row 1	1	1 + 1 = 2	2 + 1 = 3
row 2	1	2 + 1 = 3	3 + 3 = 6

Now add obstacles, squares you may not step on. The only change is that a blocked square gets 0 routes, so nothing flows through it. Block the centre and trace again: the centre becomes 0, so the cell to its right gets 0 + 1 = 1, the cell below gets 0 + 1 = 1, and the corner gets 1 + 1 = 2.

pythonrunnable cell

def unique_paths(rows, cols, blocked=()):
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if (r, c) in blocked:
                dp[r][c] = 0                        # nothing flows through a wall
            elif r == 0 and c == 0:
                dp[r][c] = 1                        # base case: the start
            else:
                up = dp[r - 1][c] if r > 0 else 0
                left = dp[r][c - 1] if c > 0 else 0
                dp[r][c] = up + left
    return dp


for row in unique_paths(3, 3):
    print(row)
print(unique_paths(3, 3)[-1][-1])
for row in unique_paths(3, 3, blocked={(1, 1)}):
    print(row)
print(unique_paths(3, 3, {(1, 1)})[-1][-1])
print(unique_paths(10, 10)[-1][-1])
# Output:
# [1, 1, 1]
# [1, 2, 3]
# [1, 3, 6]
# 6
# [1, 1, 1]
# [1, 0, 1]
# [1, 1, 2]
# 2
# 48620

Minimum path sum swaps counting for cost. Each square has a number, and you want the route from top-left to bottom-right with the smallest total. The transition becomes dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]), and an edge square has only one choice.

Trace the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]]. Row 0 adds along the edge: 1, 4, 5. Column 0 does the same: 1, 2, 6.

Cell (1,1) is 5 + min(4, 2) = 7. Cell (1,2) is 1 + min(5, 7) = 6. Cell (2,1) is 2 + min(7, 6) = 8. Cell (2,2) is 1 + min(6, 8) = 7.

pythonrunnable cell

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]      # top edge: only from the left
            elif c == 0:
                dp[r][c] = dp[r - 1][c] + grid[r][c]      # left edge: only from above
            else:
                dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c]
    return dp


table = min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])
for row in table:
    print(row)
print(table[-1][-1])
# Output:
# [1, 4, 5]
# [2, 7, 6]
# [6, 8, 7]
# 7

Both grids take O(rows * cols) time, one step per cell, and O(rows * cols) space for the table. The order is safe because every move goes right or down, so above and left always come before the cell that needs them. If moves could also go up or left, a cell could depend on a later one, and this table would no longer work. That is a job for a shortest-path algorithm instead.

#Longest Increasing Subsequence: O(n²), Then O(n log n)

A subsequence keeps the original order but may skip items. An increasing one has each value larger than the one before. In [10, 9, 2, 5, 3, 7, 101, 18] the values 2, 3, 7, 18 form one, and the longest has length 4. Part 2 gave you the code. Here we look at why it works, and fix its details.

The slow way uses the five questions. State: dp[i] is the length of the longest increasing subsequence that ends exactly at position i. Transition: look at every earlier j with a smaller value and extend the best one, so dp[i] = 1 + max(dp[j]). Base: every item alone is length 1. Answer: the largest value in dp, because the best one may end anywhere.

Trace dp by hand. Position 0 (value 10): 1. Position 1 (9): nothing smaller before it, so 1. Position 2 (2): 1. Position 3 (5): can follow 2, so 2. Position 4 (3): can follow 2, so 2. Position 5 (7): can follow 5 or 3, so 3. Position 6 (101): follows 7, so 4. Position 7 (18): follows 7, so 4.

pythonrunnable cell

def lis_table(nums):
    n = len(nums)
    dp = [1] * n                              # every item alone has length 1
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return dp


dp = lis_table([10, 9, 2, 5, 3, 7, 101, 18])
print(dp, max(dp))
# Output:
# [1, 1, 1, 2, 2, 3, 4, 4] 4

Each of the n positions looks back over up to n earlier ones, so time is O(n²) and space is O(n).

The fast way keeps a different list. Let tails[k] be the smallest value that any increasing subsequence of length k + 1 can end with. A smaller tail is better, because it leaves more room to grow. The list tails is always sorted, so you can find where a new value belongs with binary search.

For each new number x, find the first tail that is x or larger. If none exists, x extends the longest subsequence, so append it. Otherwise replace that tail with x, a smaller ending for the same length. Trace the same input; each row shows tails after reading one number.

x	what happens	tails
10	list empty, append	[10]
9	replaces 10	[9]
2	replaces 9	[2]
5	bigger than all, append	[2, 5]
3	replaces 5	[2, 3]
7	append	[2, 3, 7]
101	append	[2, 3, 7, 101]
18	replaces 101	[2, 3, 7, 18]

The answer is the length of tails, here 4.

pythonrunnable cell

import bisect


def lis_fast(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)     # first tail that is x or larger
        if pos == len(tails):
            tails.append(x)                    # x extends the longest one
        else:
            tails[pos] = x                     # a smaller ending for that length
    return len(tails)


print(lis_fast([10, 9, 2, 5, 3, 7, 101, 18]))
print(lis_fast([2, 2, 2]))
# Output:
# 4
# 1

Each number costs one binary search over a list of at most n values, so time is O(n log n). Space is O(n) for tails. The word bisect_left matters. It makes an equal value replace instead of extend, which gives a strictly increasing answer. For a non-decreasing answer, where equal values may repeat, use bisect_right.

One trap: tails is a count, not the subsequence. For [3, 5, 1] it ends as [1, 5], and 5 comes before 1 in the input. To get a real subsequence you need the table version with a record of where each length came from. The reconstruction section does that.

#Interval DP: Burst Balloons and Palindrome Cuts

An interval DP has a cell for each slice [i, j] of a sequence. A big slice is solved by splitting it at some point k and combining the two smaller slices. Because small slices must come first, you fill the table by increasing length, not row by row.

Start with burst balloons. You have balloons with numbers on them. Bursting balloon k pays the number on k times the numbers on its two current neighbours. The edges count as a balloon numbered 1. What is the most coins you can collect by bursting them all?

The key idea is to think about the last balloon to burst, not the first. If balloon k is the last one burst between i and j, its neighbours at that moment are exactly i and j. The left part and the right part are then separate problems.

State: dp[i][j] is the most coins from bursting everything strictly between i and j. Transition: try every k between them, and take dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]. Base: slices with nothing between are 0.

Trace for balloons [3, 1, 5]. Pad with 1s to get [1, 3, 1, 5, 1], positions 0 to 4. Length-2 slices have one balloon between: dp[0][2] = 1*3*1 = 3, dp[1][3] = 3*1*5 = 15, dp[2][4] = 1*5*1 = 5.

Length-3 slices: for dp[0][3], k=1 gives 0 + 135 + 15 = 30 and k=2 gives 3 + 115 + 0 = 8, so 30. For dp[1][4], k=2 gives 0 + 311 + 5 = 8 and k=3 gives 15 + 351 + 0 = 30, so 30.

The full slice: k=1 gives 0 + 131 + 30 = 33, k=2 gives 3 + 111 + 5 = 9, k=3 gives 30 + 151 + 0 = 35. The answer is 35.

pythonrunnable cell

def burst(balloons):
    nums = [1] + balloons + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for gap in range(2, n):                    # slice length, smallest first
        for i in range(n - gap):
            j = i + gap
            for k in range(i + 1, j):          # k is the last balloon burst
                coins = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
    return dp


table = burst([3, 1, 5])
for row in table:
    print(row)
print(table[0][-1], burst([3, 1, 5, 8])[0][-1])
# Output:
# [0, 0, 3, 30, 35]
# [0, 0, 0, 15, 30]
# [0, 0, 0, 0, 5]
# [0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0]
# 35 167

There are about n² slices, and each tries up to n split points, so time is O(n³). Space is O(n²) for the table.

The second interval problem is palindrome cuts. A palindrome reads the same forward and backward. What is the fewest cuts that split a string into palindromes? For "aab" the answer is 1, giving "aa" and "b".

It needs two tables. First, pal[i][j] says whether the slice s[i..j] is a palindrome. The ends must match, and the inside s[i+1..j-1] must be a palindrome too. That inside slice is shorter, so i runs from the end backward. Second, cuts[j] is the fewest cuts for the first j + 1 letters: zero if the whole prefix is a palindrome, otherwise try every last piece s[i..j] that is a palindrome.

For "aab", the palindrome table has True at (0,0), (0,1), (1,1) and (2,2). So cuts[0] = 0, cuts[1] = 0 since "aa" is a palindrome, and cuts[2] = cuts[1] + 1 = 1 using the last piece "b".

pythonrunnable cell

def min_cuts(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):             # row i needs row i + 1 first
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
    cuts = [0] * n
    for j in range(n):
        if pal[0][j]:
            cuts[j] = 0
        else:
            cuts[j] = min(cuts[i - 1] + 1 for i in range(1, j + 1) if pal[i][j])
    return cuts


for word in ("aab", "aabbc", "abcba", "abc"):
    print(word, min_cuts(word))
# Output:
# aab [0, 0, 1]
# aabbc [0, 0, 1, 1, 2]
# abcba [0, 1, 2, 1, 0]
# abc [0, 1, 2]

Filling pal is O(n²) time and space, and the cuts loop is O(n²) time. The total is O(n²) time and O(n²) space.

#Bitmask DP: The Small Travelling Salesman

Sometimes the state is a set: which items have I already used? For a small number of items, a whole number can hold the set. This is a bitmask. Write the number in binary, and let bit i be 1 when item i is in the set. The mask 0b101 is the set of items 0 and 2. Three operations are all you need:

Want	Code	Example, mask = 0b101
Is item i in the set?	`(mask >> i) & 1`	item 2 gives 1
Add item i	`mask \| (1 << i)`	add item 1
Remove item i	`mask & ~(1 << i)`	remove item 0

These are the bit operations from the Bit Manipulation lesson later in this part, which covers them in full. Here is a prediction.

What Do You Think?

The mask 0b101 (the number 5) means cities 0 and 2 are visited. You now visit city 1. What number is the new mask?

Now the problem. A salesman must visit every city once and come back to the start. He knows the distance between each pair of cities. What is the shortest round trip? This is the travelling salesman problem. Trying every order means (n - 1)! routes, which is hopeless past about 12 cities.

The DP notices that the future of a trip depends only on which cities are done and where you stand now.

The five questions. State: dp[mask][last] is the cheapest cost to start at city 0, visit exactly the cities in mask, and end at last. Transition: from (mask, last) move to an unvisited nxt, giving dp[mask | 1<<nxt][nxt] = dp[mask][last] + dist[last][nxt]. Base: dp[1][0] = 0, which means only city 0 visited. Order: masks in increasing numeric order, because adding a bit always makes the number larger. Answer: over all last, the cheapest dp[full][last] + dist[last][0].

Trace four cities with distances 0-1: 10, 0-2: 15, 0-3: 20, 1-2: 35, 1-3: 25, 2-3: 30. Read each mask right to left, so 0111 is cities 0, 1 and 2.

mask	last	cost	how
0001	0	0	base case
0011	1	10	0 to 1
0101	2	15	0 to 2
1001	3	20	0 to 3
0111	1	50	0, 2, 1 = 15 + 35
0111	2	45	0, 1, 2 = 10 + 35
1111	1	70	best way to finish at 1
1111	2	65	best way to finish at 2
1111	3	75	best way to finish at 3

Closing the loop: 70 + 10 = 80, 65 + 15 = 80, 75 + 20 = 95. The answer is 80.

pythonrunnable cell

def tsp(dist):
    n = len(dist)
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0                                   # only city 0 visited, standing there
    for mask in range(1 << n):
        for last in range(n):
            if not (mask >> last) & 1 or dp[mask][last] == INF:
                continue
            for nxt in range(n):
                if (mask >> nxt) & 1:
                    continue                       # already visited
                new_mask = mask | (1 << nxt)
                cost = dp[mask][last] + dist[last][nxt]
                if cost < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = cost
    full = (1 << n) - 1
    return min(dp[full][last] + dist[last][0] for last in range(1, n))


dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
print(tsp(dist))
# Output:
# 80

There are 2^n masks and n values of last, so 2^n * n states. Each tries up to n next cities, so time is O(2^n * n²). Space is O(2^n * n). Compare that with the (n - 1)! routes of brute force.

pythonrunnable cell

import math

for n in (4, 10, 15, 20):
    print(f"{n:>2} {math.factorial(n - 1):>20,} {2**n * n * n:>14,}")
# Output:
#  4                    6            256
# 10              362,880        102,400
# 15       87,178,291,200      7,372,800
# 20  121,645,100,408,832,000    419,430,400

The second column is routes by brute force. The third is steps for the bitmask DP. At 20 cities the DP does hundreds of millions of times fewer steps, yet its table holds about 21 million entries. At 25 cities the table would hold over 800 million, so memory becomes the wall. Bitmask DP is for small n only, and it is still exponential. The travelling salesman problem is NP-hard, so no known method avoids this blow-up.

#DP on Trees

Sometimes the "grid" is a tree. A tree is nodes joined by links, with a root at the top and each node having up to two children, the nodes directly below it. Here the street of houses is a tree: robbing a house forbids robbing its parent and its children.

The state needs two numbers per node, because the answer depends on whether the parent was robbed.

State: for each node, a pair (take, skip), the best total in its subtree if this node is robbed or not.

Transition: take = value + skip_left + skip_right, since robbing the node forces its children to be skipped. skip = max(take_left, skip_left) + max(take_right, skip_right), since a skipped node leaves each child free. Base: an empty child is (0, 0). Order: children before parents, which is a post-order walk (visit both children, then the node). Answer: the larger of the root's pair.

Trace a tree with root 3. Its left child is 2 with a right child 3. Its right child is 3 with a right child 1.

The leaves 3 and 1 return (3, 0) and (1, 0). Node 2 has child pair (3, 0): take = 2 + 0 = 2, skip = max(3, 0) = 3, so (2, 3).

The right 3 has child pair (1, 0): take = 3 + 0 = 3, skip = 1, so (3, 1). At the root: take = 3 + 3 + 1 = 7 and skip = max(2, 3) + max(3, 1) = 6. The answer is 7.

pythonrunnable cell

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def rob_tree(root):
    def go(node):
        if node is None:
            return 0, 0                            # base case: an empty child
        take_l, skip_l = go(node.left)
        take_r, skip_r = go(node.right)
        take = node.value + skip_l + skip_r        # rob it: children must be skipped
        skip = max(take_l, skip_l) + max(take_r, skip_r)
        return take, skip

    return max(go(root))


root = Node(3, Node(2, None, Node(3)), Node(3, None, Node(1)))
print(rob_tree(root))
# Output:
# 7

Every node is visited once, so time is O(n). The extra space is O(h), where h is the height of the tree, for the recursion stack. There is no table at all, because the tree is the table. The same shape (a small tuple returned up the tree) solves tree diameter, the largest independent set and many tree questions.

#Rolling Rows: Saving Space

Look back at the grid. Row r reads only row r - 1 and the cells already filled in row r. Once row r is done, rows before r - 1 are never read again, so keeping them wastes memory. A rolling row keeps just one list and overwrites it as it goes.

Here is the minimum path sum with one list of cols cells. Before the update, row[c] still holds the value from the row above. After the update, it holds the current row. Watch the list after each grid row: after row 0 it is [1, 4, 5], after row 1 it is [2, 7, 6], and after row 2 it is [6, 8, 7]. These are the same rows as the full table.

pythonrunnable cell

def min_path_sum_row(grid):
    cols = len(grid[0])
    row = [0] * cols
    for r, line in enumerate(grid):
        for c in range(cols):
            if r == 0 and c == 0:
                row[c] = line[c]
            elif r == 0:
                row[c] = row[c - 1] + line[c]            # top row: from the left
            elif c == 0:
                row[c] = row[c] + line[c]                # row[c] still holds the cell above
            else:
                row[c] = min(row[c], row[c - 1]) + line[c]
    return row[-1]


print(min_path_sum_row([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
# Output:
# 7

Time stays O(rows * cols). Space drops from O(rows * cols) to O(cols). The house robber shrinks even more, because best[i] reads only the last two cells. Two variables replace the whole list.

pythonrunnable cell

def rob_two_vars(money):
    prev2 = prev1 = 0                          # best two houses back, best one house back
    for m in money:
        prev2, prev1 = prev1, max(prev1, prev2 + m)
    return prev1


print(rob_two_vars([2, 7, 9, 3, 1]), rob_two_vars([]), rob_two_vars([4]))
# Output:
# 12 0 4

That is O(n) time and O(1) space. There is a price. After rolling, the old rows are gone, so you can no longer walk back through the table to find which route won. If you need the route, keep the full table or store the choice made at each cell.

#Reconstructing the Answer

So far the tables gave a number. Real questions often want the thing itself: the route, the subsequence, the list of items. The table already holds what you need, because each cell was built from a choice. There are two ways to recover the choices.

The first is a walk back. Start at the answer cell, and at each step ask which neighbour this value came from, then step there. For minimum path sum, a cell came from whichever of the above and left cells is smaller.

In the table from earlier, start at the corner with 7. Above it is 6 and left of it is 8, so step up. At the cell with 6, above is 5 and left is 7, so step up again. The top row has only one way back, left, twice. The route is the cells (0,0), (0,1), (0,2), (1,2), (2,2).

pythonrunnable cell

def route_of(grid):
    dp = min_path_sum(grid)                    # the full table from the grid section
    r, c = len(grid) - 1, len(grid[0]) - 1
    cells = [(r, c)]
    while (r, c) != (0, 0):
        if r == 0:
            c -= 1
        elif c == 0:
            r -= 1
        elif dp[r - 1][c] <= dp[r][c - 1]:     # step to the cheaper neighbour
            r -= 1
        else:
            c -= 1
        cells.append((r, c))
    cells.reverse()
    return cells


grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
route = route_of(grid)
print(route)
print([grid[r][c] for r, c in route])
# Output:
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
# [1, 3, 1, 1, 1]

The walk back costs O(rows + cols) extra. The values sum to 7, matching the table.

The second way is a parent array: while filling, remember in a second array which choice won. For the increasing subsequence, prev[i] is the position that i followed.

Trace the earlier dp, [1, 1, 1, 2, 2, 3, 4, 4]. The first position with the largest value 4 is position 6 (value 101). Its parent is position 5 (value 7), whose parent is position 3 (value 5), whose parent is position 2 (value 2), which has none. Read backward and reverse: 2, 5, 7, 101.

pythonrunnable cell

def lis_path(nums):
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n                            # prev[i] = the position that i follows
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    end = max(range(n), key=lambda i: dp[i]) if n else -1
    path = []
    while end != -1:
        path.append(nums[end])
        end = prev[end]
    return path[::-1]


print(lis_path([10, 9, 2, 5, 3, 7, 101, 18]))
print(lis_path([]))
# Output:
# [2, 5, 7, 101]
# []

The extra space is O(n), and the time stays O(n²). Note that 2, 3, 7, 18 is also a longest one. Ties can be broken either way, so any correct answer is fine. When a problem has several best answers, check the length or the total, not the exact route.

#DP, Greedy, Backtracking or Plain Recursion?

Four tools solve problems built from smaller choices. Choosing among them takes four questions, asked in order.

Do the same smaller questions come back again and again? If not, plain recursion is enough. Sorting by splitting in half and summing a tree never repeat a question, so a cache would store answers nobody asks for twice.
Do you need every answer listed? Then use backtracking (Backtracking), because the output itself is the work.
Is there a rule that picks the best choice at each step, and can you argue it is safe? Then greedy is faster, and a later lesson shows the proof method.
Otherwise, if the question asks for a count or a best value and the state is small, use DP.

The greedy rule needs the proof, because a rule that looks right can fail. Predict one.

What Do You Think?

Coins are 1, 3 and 4, and the amount is 6. The greedy rule takes the biggest coin that fits, again and again. How many coins does greedy use, compared with the best possible answer?

pythonrunnable cell

def greedy_coins(coins, amount):
    count = 0
    for coin in sorted(coins, reverse=True):
        take, amount = divmod(amount, coin)
        count += take
    return count if amount == 0 else -1


def dp_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1


print(greedy_coins([1, 3, 4], 6), dp_coins([1, 3, 4], 6))
print(greedy_coins([1, 5, 10, 25], 41), dp_coins([1, 5, 10, 25], 41))
# Output:
# 3 2
# 4 4

For the coins 1, 5, 10 and 25 greedy happens to be right, so a rule that works on one set of inputs is no proof. Now the first question in numbers. Plain recursion for unique paths on a 10 by 10 grid recomputes the same cells over and over. A cache fixes it.

pythonrunnable cell

from functools import lru_cache

calls = 0


def paths_plain(r, c):
    global calls
    calls += 1
    if r == 0 or c == 0:
        return 1
    return paths_plain(r - 1, c) + paths_plain(r, c - 1)


@lru_cache(maxsize=None)
def paths_cached(r, c):
    if r == 0 or c == 0:
        return 1
    return paths_cached(r - 1, c) + paths_cached(r, c - 1)


print(paths_plain(9, 9), calls)
print(paths_cached(9, 9), paths_cached.cache_info().misses)
# Output:
# 48620 97239
# 48620 99

Same answer, 97,239 calls against 99 distinct ones. That gap is what overlapping subproblems means.

#Where This Shows Up in ML

The grid fill is not only for puzzles.

The Viterbi algorithm decodes a hidden Markov model, for example the most likely tags for a sentence. It fills a table with one column per word and one row per tag, and each cell takes the best of the previous column.

Sequence alignment in biology and the loss used to train some speech models fill similar tables. Edit distance and longest common subsequence sit under diff tools and spell checkers. When you meet such a table in a paper, ask the five questions of it.

#Common Mistakes

Watch Out

Building the grid with [[0] * cols] * rows

Fix: Write [[0] * cols for _ in range(rows)]. The comprehension runs the inner expression once per row, so every row is its own list.

pythonrunnable cell

grid = [[0] * 3] * 2
grid[0][0] = 7
print(grid)
print(grid[0] is grid[1])
# Output:
# [[7, 0, 0], [7, 0, 0]]
# True

The multiplication copies the reference to one list, not the list. Both rows are the same object, so changing one changes both. In a DP table this makes cells overwrite each other, and the answers come out wrong without any error.

Watch Out

Using bisect_right when the subsequence must be strictly increasing

Fix: Use bisect_left for strictly increasing and bisect_right for non-decreasing. The question's wording about equal values decides.

pythonrunnable cell

import bisect


def lis_wrong(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_right(tails, x)      # should be bisect_left
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)


print(lis_wrong([2, 2, 2]), lis_wrong([10, 9, 2, 5, 3, 7, 101, 18]))
# Output:
# 3 4

The second answer looks right, which hides the bug. For [2, 2, 2] the strictly increasing answer is 1, not 3, because no value is larger than the one before. The test that catches it is an input with repeated values.

Watch Out

Filling an interval table row by row instead of by length

Fix: Loop over the slice length first, smallest to largest, then over the start position. Every smaller slice is then ready before a larger one needs it.

pythonrunnable cell

def burst_wrong(balloons):
    nums = [1] + balloons + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 2, n):
            for k in range(i + 1, 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]


print(burst_wrong([3, 1, 5]))
# Output:
# 20

The right answer is 35. Row i = 0 is filled first, but it reads dp[k][j] for later rows, which are still 0. Wrong numbers flow upward silently. Whenever a cell reads a cell that is not filled yet, the order question was answered wrongly.

#Try It: The Five-Problem Ladder

Five problems, easy to hard. Fill each TODO and run. The solution shows full answers, so read only the function you are stuck on, close it and write it again. Trace a tiny input by hand first.

Minimum cost climbing stairs: the five questions on a line.
Longest non-decreasing subsequence: the bisect twist.
Best route through a grid: maximum sum, and the route itself.
Find the bugs: a grid paths function with two mistakes from this lesson.
Longest palindromic subsequence: an interval table filled by length.

pythonplayground.py · Pyodide

import bisect

# 1. Min cost climbing stairs. cost[i] is the price to leave step i, and you may climb 1 or 2 steps.
#    You may start on step 0 or step 1. You finish when you stand past the last step (index n).
#    State: best[i] = cheapest way to stand on step i.  best[0] = best[1] = 0.
def min_cost_climbing(cost):
  n = len(cost)
  best = [0] * (n + 1)
  # TODO: for i from 2 to n, best[i] is the cheaper of arriving from step i-1 or from step i-2
  return best[n]

# 2. Longest NON-decreasing subsequence in O(n log n). Equal values may repeat: [2, 2, 2] has length 3.
def longest_non_decreasing(nums):
  tails = []
  # TODO: for each x, find its place in tails with the right bisect function
  #       (append if it goes at the end, otherwise replace that tail)
  return len(tails)

# 3. Best route. Move only right or down. Return (largest sum, the values along that route).
def best_route(grid):
  rows, cols = len(grid), len(grid[0])
  dp = [[0] * cols for _ in range(rows)]
  # TODO: fill dp with the largest sum that reaches each square
  # TODO: walk back from the bottom-right square, stepping to the larger neighbour, to collect the route
  return dp[-1][-1], []

# 4. Find the bugs. grid_paths(3, 3) should be 6, grid_paths(4, 4) should be 20 and grid_paths(1, 5) should be 1.
#    There are two bugs, both from this lesson.
def grid_paths(rows, cols):
  dp = [[1] * cols] * rows
  for r in range(rows):
      for c in range(cols):
          dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
  return dp[-1][-1]

# 5. Longest palindromic subsequence of a string (letters may be skipped, order is kept).
#    State: dp[i][j] = longest palindromic subsequence of s[i..j].
#    If s[i] == s[j] it is dp[i+1][j-1] + 2, otherwise the larger of dp[i+1][j] and dp[i][j-1].
def longest_palindromic_subsequence(s):
  n = len(s)
  dp = [[0] * n for _ in range(n)]
  # TODO: loop i from n-1 down to 0 so row i+1 is ready; set dp[i][i] = 1; then fill j from i+1 to n-1
  return dp[0][n - 1] if n else 0

print(min_cost_climbing([10, 15, 20]), min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
print(longest_non_decreasing([1, 3, 3, 2, 4]), longest_non_decreasing([2, 2, 2]), longest_non_decreasing([5, 4, 3]))
print(best_route([[5, 1, 2], [2, 9, 1], [1, 3, 7]]))
print(grid_paths(3, 3), grid_paths(4, 4), grid_paths(1, 5))
print(longest_palindromic_subsequence("bbbab"), longest_palindromic_subsequence("cbbd"), longest_palindromic_subsequence("abcda"))

Tests · Correct output, line by line: 15 6; 4 3 1; (26, [5, 2, 9, 3, 7]); 6 20 1; 4 2 3.

Costs for the ladder, with reasons. Problem 1 is O(n) time and O(n) space, one step per cell. Problem 2 is O(n log n) time, because each number needs one binary search, and O(n) space. Problem 3 is O(rows * cols) time and space, plus O(rows + cols) for the walk back. Problem 4 is O(rows * cols) once fixed. Problem 5 is O(n²) time and space, because there are about n²/2 slices and each takes constant work.

#Recap

The five questions (state, transition, base case, order, answer) design any dynamic program. A good state remembers exactly what the future needs.

Grid DP builds a cell from the cell above and the cell to the left, in O(rows * cols). Longest increasing subsequence is O(n²) with a table and O(n log n) with a sorted tails list and bisect. Interval DP fills slices by increasing length in O(n³) for burst balloons. A bitmask stores a set of items in one number and solves a small travelling salesman in O(2^n * n²). Tree DP returns a small tuple from each node.

Rolling rows cut the space but throw away the route. To rebuild the answer, walk back through the table or keep a parent array. To choose a tool: no repeats means plain recursion, every answer means backtracking, a provably safe local rule means greedy, and a count or best value with a small state means DP.

Quick Check1 / 6

Which of the five design questions is about making sure each cell's inputs are already filled when you reach it?

Recap

Key Takeaways

Design every DP with five questions: state, transition, base case, order and answer, and write the state as a sentence first
A grid cell is built from the cell above and the cell to its left, so row by row is a safe order and a blocked square holds 0
The tails list gives the longest increasing subsequence in O(n log n), with bisect_left for strict and bisect_right for non-decreasing
Interval DP fills slices by increasing length, thinks about the last choice in a slice, and costs O(n³) when each slice tries n splits
A bitmask holds a set of up to about 20 items in one number, which turns a (n - 1)! search into O(2^n * n²)
Rolling rows cut the space but lose the route, so rebuild the answer by walking back or keep a parent array, and check greedy with a counterexample before you trust it

DP Patterns, Part 2: Grids, Intervals, Bitmasks and Trees

Learning Objectives

After this lesson, you will be able to:

Design a dynamic program from a blank page with five questions: state, transition, base case, order and answer
Solve grid problems (unique paths, with obstacles, minimum path sum) and say why the fill order is safe
Explain why the tails list gives the longest increasing subsequence in O(n log n), and when to use bisect_left or bisect_right
Fill an interval table by increasing length for burst balloons and palindrome cuts, and state the O(n³) cost
Use a whole number as a set of visited items (a bitmask) to solve a small travelling salesman, and say when it stops being possible
Shrink a table to one row, rebuild the actual answer and not just its value, and choose between DP, greedy, backtracking and plain recursion

Prerequisites

Before You Start

Review

#Quick Recap: What Part 2 Taught

Five lines are enough. If any feels shaky, open the linked lesson first.

Dynamic programming (DP) solves a big problem from the answers to smaller versions of itself, and each small answer is stored so it is computed only once (Recursion and DP).
Memoization is top-down: write the recursion and cache each result by its arguments.
Tabulation is bottom-up: fill a table in an order where every cell's inputs are already there.
The classics (coin change, knapsack, longest common subsequence, edit distance) are one technique used four times (Part 2).
A table of m by n cells costs O(m * n) time, and keeping only the rows you still need can cut the space.

#The Design Method: Five Questions

When a DP problem looks new, do not hunt for a trick. Answer five questions, in this order.

State. What does one cell of the table mean? Write it as a sentence, such as "best[i] is the most money from the first i houses".
Transition. How is one cell built from smaller cells? This is the recurrence, and it is nearly always a min, a max or a sum over a few choices.
Base case. Which cells have an answer you know without computing, such as the empty prefix?
Order. In what order can you fill the cells so each one's inputs are ready?
Answer. Which cell holds what the question asked for?

State: best[i] is the most money from the first i houses.
Transition: either skip house i and keep best[i-1], or rob it and add best[i-2], because the neighbour is off limits.
Base case: best[0] = 0, since no houses means no money.
Order: left to right.
Answer: best[n].

Trace it by hand for [2, 7, 9, 3, 1] before reading any code. One row is one house.

i	money	skip: best[i-1]	rob: money + best[i-2]	best[i]
1	2	0	2 + 0 = 2	2
2	7	2	7 + 0 = 7	7
3	9	7	9 + 2 = 11	11
4	3	11	3 + 7 = 10	11
5	1	11	1 + 11 = 12	12

The answer is the last cell. Notice row 4: robbing house 4 would give 10, skipping gives 11, so the best stays 11.

pythonrunnable cell

def rob(money):
    n = len(money)
    best = [0] * (n + 1)                   # best[0] = 0 is the base case
    for i in range(1, n + 1):
        take = money[i - 1] + (best[i - 2] if i >= 2 else 0)
        best[i] = max(best[i - 1], take)   # skip the house, or rob it
    return best


print(rob([2, 7, 9, 3, 1]))
print(rob([5]), rob([]))
# Output:
# [0, 2, 7, 11, 11, 12]
# [0, 5] [0]

The time is O(n), one step per cell, and the space is O(n) for the table. Keep this recipe. Every section below is the same five questions with a different state.

#Grid DP: Unique Paths, Obstacles and Minimum Path Sum

A grid DP has a cell for each square of a grid, and a cell is built from the cell above it and the cell to its left. Start with a prediction.

What Do You Think?

A robot stands in the top-left square of a 3 by 3 grid. It may move only right or down. It must reach the bottom-right square. How many different routes are there?

Fill a 3 by 3 grid by hand. The first row and first column are all 1, because there is only one way along an edge.

	col 0	col 1	col 2
row 0	1	1	1
row 1	1	1 + 1 = 2	2 + 1 = 3
row 2	1	2 + 1 = 3	3 + 3 = 6

pythonrunnable cell

def unique_paths(rows, cols, blocked=()):
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if (r, c) in blocked:
                dp[r][c] = 0                        # nothing flows through a wall
            elif r == 0 and c == 0:
                dp[r][c] = 1                        # base case: the start
            else:
                up = dp[r - 1][c] if r > 0 else 0
                left = dp[r][c - 1] if c > 0 else 0
                dp[r][c] = up + left
    return dp


for row in unique_paths(3, 3):
    print(row)
print(unique_paths(3, 3)[-1][-1])
for row in unique_paths(3, 3, blocked={(1, 1)}):
    print(row)
print(unique_paths(3, 3, {(1, 1)})[-1][-1])
print(unique_paths(10, 10)[-1][-1])
# Output:
# [1, 1, 1]
# [1, 2, 3]
# [1, 3, 6]
# 6
# [1, 1, 1]
# [1, 0, 1]
# [1, 1, 2]
# 2
# 48620

Trace the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]]. Row 0 adds along the edge: 1, 4, 5. Column 0 does the same: 1, 2, 6.

Cell (1,1) is 5 + min(4, 2) = 7. Cell (1,2) is 1 + min(5, 7) = 6. Cell (2,1) is 2 + min(7, 6) = 8. Cell (2,2) is 1 + min(6, 8) = 7.

pythonrunnable cell

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]      # top edge: only from the left
            elif c == 0:
                dp[r][c] = dp[r - 1][c] + grid[r][c]      # left edge: only from above
            else:
                dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c]
    return dp


table = min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])
for row in table:
    print(row)
print(table[-1][-1])
# Output:
# [1, 4, 5]
# [2, 7, 6]
# [6, 8, 7]
# 7

#Longest Increasing Subsequence: O(n²), Then O(n log n)

pythonrunnable cell

def lis_table(nums):
    n = len(nums)
    dp = [1] * n                              # every item alone has length 1
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return dp


dp = lis_table([10, 9, 2, 5, 3, 7, 101, 18])
print(dp, max(dp))
# Output:
# [1, 1, 1, 2, 2, 3, 4, 4] 4

Each of the n positions looks back over up to n earlier ones, so time is O(n²) and space is O(n).

x	what happens	tails
10	list empty, append	[10]
9	replaces 10	[9]
2	replaces 9	[2]
5	bigger than all, append	[2, 5]
3	replaces 5	[2, 3]
7	append	[2, 3, 7]
101	append	[2, 3, 7, 101]
18	replaces 101	[2, 3, 7, 18]

The answer is the length of tails, here 4.

pythonrunnable cell

import bisect


def lis_fast(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)     # first tail that is x or larger
        if pos == len(tails):
            tails.append(x)                    # x extends the longest one
        else:
            tails[pos] = x                     # a smaller ending for that length
    return len(tails)


print(lis_fast([10, 9, 2, 5, 3, 7, 101, 18]))
print(lis_fast([2, 2, 2]))
# Output:
# 4
# 1

#Interval DP: Burst Balloons and Palindrome Cuts

Length-3 slices: for dp[0][3], k=1 gives 0 + 135 + 15 = 30 and k=2 gives 3 + 115 + 0 = 8, so 30. For dp[1][4], k=2 gives 0 + 311 + 5 = 8 and k=3 gives 15 + 351 + 0 = 30, so 30.

The full slice: k=1 gives 0 + 131 + 30 = 33, k=2 gives 3 + 111 + 5 = 9, k=3 gives 30 + 151 + 0 = 35. The answer is 35.

pythonrunnable cell

def burst(balloons):
    nums = [1] + balloons + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for gap in range(2, n):                    # slice length, smallest first
        for i in range(n - gap):
            j = i + gap
            for k in range(i + 1, j):          # k is the last balloon burst
                coins = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
    return dp


table = burst([3, 1, 5])
for row in table:
    print(row)
print(table[0][-1], burst([3, 1, 5, 8])[0][-1])
# Output:
# [0, 0, 3, 30, 35]
# [0, 0, 0, 15, 30]
# [0, 0, 0, 0, 5]
# [0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0]
# 35 167

There are about n² slices, and each tries up to n split points, so time is O(n³). Space is O(n²) for the table.

For "aab", the palindrome table has True at (0,0), (0,1), (1,1) and (2,2). So cuts[0] = 0, cuts[1] = 0 since "aa" is a palindrome, and cuts[2] = cuts[1] + 1 = 1 using the last piece "b".

pythonrunnable cell

def min_cuts(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):             # row i needs row i + 1 first
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
    cuts = [0] * n
    for j in range(n):
        if pal[0][j]:
            cuts[j] = 0
        else:
            cuts[j] = min(cuts[i - 1] + 1 for i in range(1, j + 1) if pal[i][j])
    return cuts


for word in ("aab", "aabbc", "abcba", "abc"):
    print(word, min_cuts(word))
# Output:
# aab [0, 0, 1]
# aabbc [0, 0, 1, 1, 2]
# abcba [0, 1, 2, 1, 0]
# abc [0, 1, 2]

Filling pal is O(n²) time and space, and the cuts loop is O(n²) time. The total is O(n²) time and O(n²) space.

#Bitmask DP: The Small Travelling Salesman

Want	Code	Example, mask = 0b101
Is item i in the set?	`(mask >> i) & 1`	item 2 gives 1
Add item i	`mask \| (1 << i)`	add item 1
Remove item i	`mask & ~(1 << i)`	remove item 0

These are the bit operations from the Bit Manipulation lesson later in this part, which covers them in full. Here is a prediction.

What Do You Think?

The mask 0b101 (the number 5) means cities 0 and 2 are visited. You now visit city 1. What number is the new mask?

The DP notices that the future of a trip depends only on which cities are done and where you stand now.

Trace four cities with distances 0-1: 10, 0-2: 15, 0-3: 20, 1-2: 35, 1-3: 25, 2-3: 30. Read each mask right to left, so 0111 is cities 0, 1 and 2.

mask	last	cost	how
0001	0	0	base case
0011	1	10	0 to 1
0101	2	15	0 to 2
1001	3	20	0 to 3
0111	1	50	0, 2, 1 = 15 + 35
0111	2	45	0, 1, 2 = 10 + 35
1111	1	70	best way to finish at 1
1111	2	65	best way to finish at 2
1111	3	75	best way to finish at 3

Closing the loop: 70 + 10 = 80, 65 + 15 = 80, 75 + 20 = 95. The answer is 80.

pythonrunnable cell

def tsp(dist):
    n = len(dist)
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0                                   # only city 0 visited, standing there
    for mask in range(1 << n):
        for last in range(n):
            if not (mask >> last) & 1 or dp[mask][last] == INF:
                continue
            for nxt in range(n):
                if (mask >> nxt) & 1:
                    continue                       # already visited
                new_mask = mask | (1 << nxt)
                cost = dp[mask][last] + dist[last][nxt]
                if cost < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = cost
    full = (1 << n) - 1
    return min(dp[full][last] + dist[last][0] for last in range(1, n))


dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
print(tsp(dist))
# Output:
# 80

There are 2^n masks and n values of last, so 2^n * n states. Each tries up to n next cities, so time is O(2^n * n²). Space is O(2^n * n). Compare that with the (n - 1)! routes of brute force.

pythonrunnable cell

import math

for n in (4, 10, 15, 20):
    print(f"{n:>2} {math.factorial(n - 1):>20,} {2**n * n * n:>14,}")
# Output:
#  4                    6            256
# 10              362,880        102,400
# 15       87,178,291,200      7,372,800
# 20  121,645,100,408,832,000    419,430,400

#DP on Trees

The state needs two numbers per node, because the answer depends on whether the parent was robbed.

State: for each node, a pair (take, skip), the best total in its subtree if this node is robbed or not.

Trace a tree with root 3. Its left child is 2 with a right child 3. Its right child is 3 with a right child 1.

The leaves 3 and 1 return (3, 0) and (1, 0). Node 2 has child pair (3, 0): take = 2 + 0 = 2, skip = max(3, 0) = 3, so (2, 3).

The right 3 has child pair (1, 0): take = 3 + 0 = 3, skip = 1, so (3, 1). At the root: take = 3 + 3 + 1 = 7 and skip = max(2, 3) + max(3, 1) = 6. The answer is 7.

pythonrunnable cell

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def rob_tree(root):
    def go(node):
        if node is None:
            return 0, 0                            # base case: an empty child
        take_l, skip_l = go(node.left)
        take_r, skip_r = go(node.right)
        take = node.value + skip_l + skip_r        # rob it: children must be skipped
        skip = max(take_l, skip_l) + max(take_r, skip_r)
        return take, skip

    return max(go(root))


root = Node(3, Node(2, None, Node(3)), Node(3, None, Node(1)))
print(rob_tree(root))
# Output:
# 7

#Rolling Rows: Saving Space

pythonrunnable cell

def min_path_sum_row(grid):
    cols = len(grid[0])
    row = [0] * cols
    for r, line in enumerate(grid):
        for c in range(cols):
            if r == 0 and c == 0:
                row[c] = line[c]
            elif r == 0:
                row[c] = row[c - 1] + line[c]            # top row: from the left
            elif c == 0:
                row[c] = row[c] + line[c]                # row[c] still holds the cell above
            else:
                row[c] = min(row[c], row[c - 1]) + line[c]
    return row[-1]


print(min_path_sum_row([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
# Output:
# 7

Time stays O(rows * cols). Space drops from O(rows * cols) to O(cols). The house robber shrinks even more, because best[i] reads only the last two cells. Two variables replace the whole list.

pythonrunnable cell

def rob_two_vars(money):
    prev2 = prev1 = 0                          # best two houses back, best one house back
    for m in money:
        prev2, prev1 = prev1, max(prev1, prev2 + m)
    return prev1


print(rob_two_vars([2, 7, 9, 3, 1]), rob_two_vars([]), rob_two_vars([4]))
# Output:
# 12 0 4

#Reconstructing the Answer

pythonrunnable cell

def route_of(grid):
    dp = min_path_sum(grid)                    # the full table from the grid section
    r, c = len(grid) - 1, len(grid[0]) - 1
    cells = [(r, c)]
    while (r, c) != (0, 0):
        if r == 0:
            c -= 1
        elif c == 0:
            r -= 1
        elif dp[r - 1][c] <= dp[r][c - 1]:     # step to the cheaper neighbour
            r -= 1
        else:
            c -= 1
        cells.append((r, c))
    cells.reverse()
    return cells


grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
route = route_of(grid)
print(route)
print([grid[r][c] for r, c in route])
# Output:
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
# [1, 3, 1, 1, 1]

The walk back costs O(rows + cols) extra. The values sum to 7, matching the table.

The second way is a parent array: while filling, remember in a second array which choice won. For the increasing subsequence, prev[i] is the position that i followed.

pythonrunnable cell

def lis_path(nums):
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n                            # prev[i] = the position that i follows
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    end = max(range(n), key=lambda i: dp[i]) if n else -1
    path = []
    while end != -1:
        path.append(nums[end])
        end = prev[end]
    return path[::-1]


print(lis_path([10, 9, 2, 5, 3, 7, 101, 18]))
print(lis_path([]))
# Output:
# [2, 5, 7, 101]
# []

#DP, Greedy, Backtracking or Plain Recursion?

Four tools solve problems built from smaller choices. Choosing among them takes four questions, asked in order.

Do the same smaller questions come back again and again? If not, plain recursion is enough. Sorting by splitting in half and summing a tree never repeat a question, so a cache would store answers nobody asks for twice.
Do you need every answer listed? Then use backtracking (Backtracking), because the output itself is the work.
Is there a rule that picks the best choice at each step, and can you argue it is safe? Then greedy is faster, and a later lesson shows the proof method.
Otherwise, if the question asks for a count or a best value and the state is small, use DP.

The greedy rule needs the proof, because a rule that looks right can fail. Predict one.

What Do You Think?

Coins are 1, 3 and 4, and the amount is 6. The greedy rule takes the biggest coin that fits, again and again. How many coins does greedy use, compared with the best possible answer?

pythonrunnable cell

def greedy_coins(coins, amount):
    count = 0
    for coin in sorted(coins, reverse=True):
        take, amount = divmod(amount, coin)
        count += take
    return count if amount == 0 else -1


def dp_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1


print(greedy_coins([1, 3, 4], 6), dp_coins([1, 3, 4], 6))
print(greedy_coins([1, 5, 10, 25], 41), dp_coins([1, 5, 10, 25], 41))
# Output:
# 3 2
# 4 4

pythonrunnable cell

from functools import lru_cache

calls = 0


def paths_plain(r, c):
    global calls
    calls += 1
    if r == 0 or c == 0:
        return 1
    return paths_plain(r - 1, c) + paths_plain(r, c - 1)


@lru_cache(maxsize=None)
def paths_cached(r, c):
    if r == 0 or c == 0:
        return 1
    return paths_cached(r - 1, c) + paths_cached(r, c - 1)


print(paths_plain(9, 9), calls)
print(paths_cached(9, 9), paths_cached.cache_info().misses)
# Output:
# 48620 97239
# 48620 99

Same answer, 97,239 calls against 99 distinct ones. That gap is what overlapping subproblems means.

#Where This Shows Up in ML

The grid fill is not only for puzzles.

#Common Mistakes

Watch Out

Building the grid with [[0] * cols] * rows

Fix: Write [[0] * cols for _ in range(rows)]. The comprehension runs the inner expression once per row, so every row is its own list.

pythonrunnable cell

grid = [[0] * 3] * 2
grid[0][0] = 7
print(grid)
print(grid[0] is grid[1])
# Output:
# [[7, 0, 0], [7, 0, 0]]
# True

Watch Out

Using bisect_right when the subsequence must be strictly increasing

Fix: Use bisect_left for strictly increasing and bisect_right for non-decreasing. The question's wording about equal values decides.

pythonrunnable cell

import bisect


def lis_wrong(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_right(tails, x)      # should be bisect_left
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)


print(lis_wrong([2, 2, 2]), lis_wrong([10, 9, 2, 5, 3, 7, 101, 18]))
# Output:
# 3 4

Watch Out

Filling an interval table row by row instead of by length

Fix: Loop over the slice length first, smallest to largest, then over the start position. Every smaller slice is then ready before a larger one needs it.

pythonrunnable cell

def burst_wrong(balloons):
    nums = [1] + balloons + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 2, n):
            for k in range(i + 1, 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]


print(burst_wrong([3, 1, 5]))
# Output:
# 20

#Try It: The Five-Problem Ladder

Five problems, easy to hard. Fill each TODO and run. The solution shows full answers, so read only the function you are stuck on, close it and write it again. Trace a tiny input by hand first.

Minimum cost climbing stairs: the five questions on a line.
Longest non-decreasing subsequence: the bisect twist.
Best route through a grid: maximum sum, and the route itself.
Find the bugs: a grid paths function with two mistakes from this lesson.
Longest palindromic subsequence: an interval table filled by length.

pythonplayground.py · Pyodide

import bisect

Tests · Correct output, line by line: 15 6; 4 3 1; (26, [5, 2, 9, 3, 7]); 6 20 1; 4 2 3.

#Recap

The five questions (state, transition, base case, order, answer) design any dynamic program. A good state remembers exactly what the future needs.

Quick Check1 / 6

Which of the five design questions is about making sure each cell's inputs are already filled when you reach it?

Recap

Key Takeaways

Design every DP with five questions: state, transition, base case, order and answer, and write the state as a sentence first
A grid cell is built from the cell above and the cell to its left, so row by row is a safe order and a blocked square holds 0
The tails list gives the longest increasing subsequence in O(n log n), with bisect_left for strict and bisect_right for non-decreasing
Interval DP fills slices by increasing length, thinks about the last choice in a slice, and costs O(n³) when each slice tries n splits
A bitmask holds a set of up to about 20 items in one number, which turns a (n - 1)! search into O(2^n * n²)
Rolling rows cut the space but lose the route, so rebuild the answer by walking back or keep a parent array, and check greedy with a counterexample before you trust it

DP Patterns, Part 2: Grids, Intervals, Bitmasks and Trees

#Quick Recap: What Part 2 Taught

#The Design Method: Five Questions

#Grid DP: Unique Paths, Obstacles and Minimum Path Sum

#Longest Increasing Subsequence: O(n²), Then O(n log n)

#Interval DP: Burst Balloons and Palindrome Cuts

#Bitmask DP: The Small Travelling Salesman

#DP on Trees

#Rolling Rows: Saving Space

#Reconstructing the Answer

#DP, Greedy, Backtracking or Plain Recursion?

#Where This Shows Up in ML

#Common Mistakes

#Try It: The Five-Problem Ladder

#Recap

Your Reflection

Continue Learning

Discussion

DP Patterns, Part 2: Grids, Intervals, Bitmasks and Trees

#Quick Recap: What Part 2 Taught

#The Design Method: Five Questions

#Grid DP: Unique Paths, Obstacles and Minimum Path Sum

#Longest Increasing Subsequence: O(n²), Then O(n log n)

#Interval DP: Burst Balloons and Palindrome Cuts

#Bitmask DP: The Small Travelling Salesman

#DP on Trees

#Rolling Rows: Saving Space

#Reconstructing the Answer

#DP, Greedy, Backtracking or Plain Recursion?

#Where This Shows Up in ML

#Common Mistakes

#Try It: The Five-Problem Ladder

#Recap

Your Reflection

Continue Learning

Discussion