Advanced Dynamic Programming — Coding Interview Patterns

By now you can define a state and a recurrence (Lessons 17–18). The DP problems that still feel impossible aren’t harder ideas — they just have a cleverer state. Three state shapes cover almost all of the hard DP you’ll see: a subset (bitmask), a range (interval), and a subtree (tree DP). Learn to recognise them and the recurrence falls out.

The idea

Bitmask DP — the state is a subset of items, packed into an integer. Viable when n ≤ ~20 (2²⁰ ≈ 1M states).
Interval DP — dp[i][j] is the answer for the sub-array i..j; you split on a middle index.
Tree DP — each node returns a small tuple; you combine children up toward the root.
Digit DP — build a number digit by digit, carrying a “still tight against the bound” flag.

Bitmask DP: the subset is the state

When n ≤ 20, “which items have I used?” fits in an integer where bit i means item i is taken. The travelling-salesman-style recurrence is dp[mask][i] = best way to have visited the set mask, currently at i:

from functools import lru_cache
def tsp(dist):                             # shortest tour visiting all n cities
    n = len(dist); FULL = (1 << n) - 1
    @lru_cache(None)
    def dp(mask, i):
        if mask == FULL:
            return dist[i][0]              # return home
        best = float('inf')
        for j in range(n):
            if not mask & (1 << j):        # j not yet visited
                best = min(best, dist[i][j] + dp(mask | (1 << j), j))
        return best
    return dp(1, 0)                        # start at city 0, only it visited
# the n <= 20 constraint is the signal to reach for a bitmask

The constraint is the giveaway: whenever you see n ≤ 20 (or ≤ 16) and “visit all / assign all / cover all”, think bitmask. There are 2ⁿ masks × n positions, so the whole table is O(2ⁿ · n).

Interval DP: build outward from small ranges

Here dp[i][j] depends on splitting the range i..j at some middle k. You fill by increasing length so the sub-ranges are ready. Burst Balloons is the canonical example — think about the balloon burst last in a range, so its neighbours are the range boundaries:

def burst_balloons(nums):
    a = [1] + nums + [1]; n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):             # range width
        for l in range(n - length):
            r = l + length
            for m in range(l + 1, r):      # m = balloon burst LAST in (l, r)
                dp[l][r] = max(dp[l][r],
                               dp[l][m] + a[l]*a[m]*a[r] + dp[m][r])
    return dp[0][n - 1]
# burst_balloons([3,1,5,8]) -> 167

The two tells for interval DP: the answer is about a contiguous range, and a naive left-to-right choice fails because the order of operations inside the range matters (matrix-chain multiplication, cutting a stick, palindrome partitioning all fit this shape).

Tree DP: return a tuple, combine upward

On a tree, the “state” is a node, and each node’s answer is built from its children’s answers via a post-order DFS. The trick is to return enough information — usually a small tuple covering the cases a parent needs. House Robber III returns (rob_this_node, skip_this_node):

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)                  # (rob this, skip this)
        l = dfs(node.left); r = dfs(node.right)
        rob_here = node.val + l[1] + r[1]  # rob node → must skip children
        skip_here = max(l) + max(r)        # skip node → children free to choose
        return (rob_here, skip_here)
    return max(dfs(root))
# tree 3 -> (2 -> _, 3), (3 -> _, 1):  rob(root) -> 7  (3 + 3 + 1)

Tree diameter, binary-tree maximum path sum (Lesson 13), and “longest path” problems are all tree DP: one DFS, each node returns what its parent needs, and a running global holds the best answer seen.

Digit DP (briefly)

For “count numbers ≤ N with some property”, build the number digit by digit with a state of (position, tight, ...property...), where tight means you’re still bounded by N’s prefix. It’s just DP over the digit positions — reach for it when the input is a number up to 10¹⁸ and you must count, not enumerate.

When to reach for it

n ≤ 20 and “visit/assign/cover all” → bitmask DP.
Answer is about a contiguous range and order-of-operations matters → interval DP (fill by length).
Input is a tree / “on the tree, pick nodes with a constraint” → tree DP (post-order, return a tuple).
“Count numbers up to N with a property” → digit DP.

Pitfalls

Bitmask that’s too big. 2ⁿ explodes past n ≈ 22. If n is larger, it isn’t bitmask DP — look for another state.
Interval DP fill order. You must fill shorter ranges before longer ones. Loop on length (or recurse with memoisation), never a plain i-then-j order.
Tree DP returning too little. If the parent needs both “used this node” and “didn’t”, return both. Returning a single number is the most common tree-DP bug.
Recursion depth. Deep trees or large bitmask recursions can hit Python’s recursion limit — mention an iterative or sys.setrecursionlimit fix.

Recap

Advanced DP is the same skill — define the state, define the recurrence — with a richer state: a subset (bitmask, when n ≤ 20), a range (interval, filled by length, split on a middle), or a subtree (tree DP, post-order, return a tuple). Recognise the shape from the constraints and the recurrence writes itself.

Practice: 10 solved problems on advanced DP → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 25 — String Algorithms.