Advanced DP (Interval, Tree, Bitmask, Digit)

Interval DP

State: dp[i][j] = answer for the contiguous segment i..j. Transition: try every split point k inside the segment, combining dp[i][k] and dp[k][j] (or dp[k+1][j]) plus a cost for the merge. Order: by increasing length, so smaller intervals are ready.

def interval_dp(n):
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j))
    return dp[0][n - 1]

Burst balloons: think about the last move

Bursting a balloon changes its neighbours' neighbours, so "first balloon burst" leads to messy subproblems. Instead choose the last balloon k to burst in the open interval (i, j): when it bursts, its neighbours are exactly i and j, and the two sides are independent.

def max_coins(nums):
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]            # dp[i][j]: open interval (i, j)
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
    return dp[0][n - 1]

int maxCoins(vector<int>& nums) {
    vector<int> a = {1};
    a.insert(a.end(), nums.begin(), nums.end());
    a.push_back(1);
    int n = a.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len < n; len++)
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++)
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
        }
    return dp[0][n - 1];
}

Game DP on intervals

Two players alternately take from either end. Let dp[i][j] = best score difference (current player − opponent) on i..j:

def stone_game_diff(piles):
    n = len(piles)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
    return dp[0][n - 1]            # > 0 → first player wins

Storing the difference makes the recurrence symmetric: after my move, the opponent's best difference is subtracted.

Tree DP

Compute answers for subtrees bottom-up (post-order); each node combines its children's results. Often each node returns several values, one per "status".

House Robber III

def rob_tree(root):
    def dfs(node):                       # returns (with node robbed, without)
        if not node:
            return 0, 0
        lr, ls = dfs(node.left)
        rr, rs = dfs(node.right)
        robbed = node.val + ls + rs
        skipped = max(lr, ls) + max(rr, rs)
        return robbed, skipped
    return max(dfs(root))

pair<int,int> dfs(TreeNode* n) {       // {robbed, skipped}
    if (!n) return {0, 0};
    auto [lr, ls] = dfs(n->left);
    auto [rr, rs] = dfs(n->right);
    return {n->val + ls + rs, max(lr, ls) + max(rr, rs)};
}
int rob(TreeNode* root) { auto [a, b] = dfs(root); return max(a, b); }

Binary tree cameras (three states)

States per node: 0 = not covered (needs the parent to cover it), 1 = has a camera, 2 = covered without a camera. Greedy post-order: put a camera on a node iff some child is uncovered.

def min_camera_cover(root):
    cams = 0
    def dfs(node):
        nonlocal cams
        if not node:
            return 2                     # null counts as covered
        l, r = dfs(node.left), dfs(node.right)
        if l == 0 or r == 0:
            cams += 1
            return 1
        if l == 1 or r == 1:
            return 2
        return 0
    return cams + (dfs(root) == 0)

Rerooting (answer for every root)

Compute an answer for one root with a DFS, then a second DFS moves the root to each child, adjusting in O(1). Sum of Distances in Tree: moving the root from p to child c brings size[c] nodes one step closer and n − size[c] nodes one step farther:

def sum_of_distances_in_tree(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    size, ans = [1] * n, [0] * n
    def dfs1(u, p, depth):
        ans[0] += depth
        for v in adj[u]:
            if v != p:
                dfs1(v, u, depth + 1)
                size[u] += size[v]
    def dfs2(u, p):
        for v in adj[u]:
            if v != p:
                ans[v] = ans[u] - size[v] + (n - size[v])
                dfs2(v, u)
    dfs1(0, -1, 0)
    dfs2(0, -1)
    return ans

(For n up to 3·10⁴, use iterative DFS or raise the recursion limit in Python.)

Bitmask DP

When n ≤ ~20, a set of items fits in an integer mask. dp[mask] or dp[mask][last] enumerates all 2ⁿ subsets.

Travelling salesman shape

def tsp(dist):
    n = len(dist)
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]      # dp[mask][last]
    dp[1][0] = 0                                  # start at node 0
    for mask in range(1 << n):
        for last in range(n):
            if dp[mask][last] == INF or not (mask >> last & 1):
                continue
            for nxt in range(n):
                if mask >> nxt & 1:
                    continue
                nm = mask | (1 << nxt)
                dp[nm][nxt] = min(dp[nm][nxt], dp[mask][last] + dist[last][nxt])
    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(n))

int tsp(vector<vector<int>>& dist) {
    int n = dist.size(), FULL = (1 << n) - 1;
    const int INF = 1e9;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;
    for (int mask = 1; mask <= FULL; mask++)
        for (int last = 0; last < n; last++) {
            if (dp[mask][last] >= INF || !(mask >> last & 1)) continue;
            for (int nxt = 0; nxt < n; nxt++) {
                if (mask >> nxt & 1) continue;
                int nm = mask | (1 << nxt);
                dp[nm][nxt] = min(dp[nm][nxt], dp[mask][last] + dist[last][nxt]);
            }
        }
    int best = INF;
    for (int i = 0; i < n; i++) best = min(best, dp[FULL][i] + dist[i][0]);
    return best;
}

Assignment: dp over the mask only

When items are processed in a fixed order (person i = popcount(mask)), you only need dp[mask]:

def min_assignment_cost(cost):             # cost[person][task], n persons = n tasks
    n = len(cost)
    dp = [float("inf")] * (1 << n)
    dp[0] = 0
    for mask in range(1 << n):
        person = bin(mask).count("1")
        if person == n:
            continue
        for task in range(n):
            if not mask >> task & 1:
                nm = mask | (1 << task)
                dp[nm] = min(dp[nm], dp[mask] + cost[person][task])
    return dp[-1]

Iterating submasks

For partition-into-groups problems, dp[mask] = min over submask s of dp[mask ^ s] + cost(s). Iterating all submasks of all masks costs O(3ⁿ).

Digit DP

Count integers in [0, N] whose digits satisfy a property (digit sum, no repeated digits, contains a 1…). Walk the digits of N from the most significant, carrying:

• pos — current digit position
• tight — whether the prefix so far equals N's prefix (limits the next digit)
• started — whether a non-zero digit has appeared (handles leading zeros)
• the property's state (sum so far, mask of used digits, last digit…)

from functools import cache

def count_special_numbers(n):           # integers in [1, n] with all distinct digits
    digits = list(map(int, str(n)))

    @cache
    def go(pos, mask, tight, started):
        if pos == len(digits):
            return 1 if started else 0
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(limit + 1):
            if started and mask >> d & 1:
                continue                             # digit already used
            now_started = started or d != 0
            new_mask = mask | (1 << d) if now_started else mask
            total += go(pos + 1, new_mask, tight and d == limit, now_started)
        return total

    return go(0, 0, True, False)

Count in a range [L, R] as f(R) − f(L − 1).

DP optimizations (awareness level)

Common mistakes

• Interval DP iterated in the wrong order (must be by length or with i descending).
• Choosing the "first" action when the "last" action gives independent subproblems.
• Tree DP returning a single value when the parent needs several statuses.
• Bitmask DP with n too large (2²⁵ × 25 is already too slow).
• Digit DP forgetting leading-zero handling or the tight flag.