Advanced DP Patterns: Bitmask, Digit, Trees & Intervals

Once you are comfortable with the classic DP patterns — knapsack, LIS, edit distance — you start encountering problems where the state space is stranger. The subproblems might be intervals of an array, subtrees of a tree, subsets encoded as bitmasks, or even individual digits of a number. This post walks through six advanced DP families that appear frequently in competitive programming and occasionally in senior-level interviews.

1. Interval DP — Matrix Chain Multiplication

The idea: the state is a contiguous subarray [i, j]. You try every possible split point k inside that range and combine the answers from [i, k] and [k+1, j].

Think of it like breaking a chocolate bar. You pick a line to snap along, solve each half, and combine. The order in which you snap matters — and that is what you are optimising.

The classic — Matrix Chain Multiplication

Given matrices A1, A2, ..., An with dimensions such that Ai is p[i-1] x p[i], find the parenthesisation that minimises total scalar multiplications.

def matrix_chain(p):
    n = len(p) - 1  # number of matrices
    # dp[i][j] = min cost to multiply matrices i..j
    dp = [[0] * n for _ in range(n)]

    # length of chain
    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):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

# Matrices: 10x30, 30x5, 5x60
print(matrix_chain([10, 30, 5, 60]))  # 4500

dp[i][j] = min over k in [i, j-1] of:
dp[i][k] + dp[k+1][j] + cost(i, k, j)
Example for 4 matrices (indices 0..3):
Length 2: dp[0][1], dp[1][2], dp[2][3]
Length 3: dp[0][2], dp[1][3]
Length 4: dp[0][3]  ← final answer

Time: O(n^3). Space: O(n^2). The key insight is filling by increasing chain length so that smaller intervals are ready when larger ones need them.

Other problems using interval DP: Burst Balloons (LeetCode 312), Palindrome Partitioning II, Optimal BST, Stone Game variants.

When to recognise it

If the problem says “merge adjacent elements” or “remove elements from an array and the cost depends on neighbours,” think interval DP.

2. DP on Trees — The Rerooting Technique

Standard tree DP computes an answer rooted at a fixed node. But some problems ask: “What is the answer if every node were the root?” Recomputing from scratch for each root costs O(n^2). The rerooting technique does it in O(n) with two DFS passes.

Example — Sum of distances to all nodes

Given an unweighted tree with n nodes, for each node compute the sum of distances to every other node.

Step 1 (root at node 0): DFS to compute subtree_size[v] and down[v] — the sum of distances from v to all nodes in its subtree.

Step 2 (reroot): DFS again. When moving the root from parent u to child v, nodes in v’s subtree get 1 closer and all other nodes get 1 farther:

answer[v] = answer[u] - subtree_size[v] + (n - subtree_size[v])

def sum_of_distances(n, edges):
    from collections import defaultdict
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    sub_size = [1] * n
    down = [0] * n
    answer = [0] * n

    # DFS 1: compute subtree sizes and down-distances
    stack = [(0, -1, False)]
    order = []
    while stack:
        node, parent, visited = stack.pop()
        if visited:
            for child in adj[node]:
                if child != parent:
                    sub_size[node] += sub_size[child]
                    down[node] += down[child] + sub_size[child]
            continue
        stack.append((node, parent, True))
        order.append((node, parent))
        for child in adj[node]:
            if child != parent:
                stack.append((child, node, False))

    # DFS 2: reroot
    answer[0] = down[0]
    for node, parent in order:
        for child in adj[node]:
            if child != parent:
                answer[child] = answer[node] - sub_size[child] + (n - sub_size[child])

    return answer

The rerooting idea applies whenever the contribution of a subtree can be “undone” and “redone” in O(1). Problems: Sum of Distances in Tree (LeetCode 834), Tree Coloring, Maximum Path queries.

3. Bitmask DP — Subsets as States

When the number of items is small (typically n < 20), you can represent a subset as a bitmask and use it as a DP state. Each bit says “is this element included?”

The Traveling Salesman Problem (TSP)

Visit every city exactly once and return to the start with minimum total distance.

State: dp[mask][i] = minimum cost to visit the set of cities in mask, ending at city i.

Transition: to reach state (mask, i), we came from some city j that is in mask but is not i:

dp[mask][i] = min over j of (dp[mask ^ (1 << i)][j] + dist[j][i])

def tsp(dist):
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask & (1 << u)):
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v],
                                      dp[mask][u] + dist[u][v])

    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(n))

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

Time: O(2^n * n^2). Space: O(2^n * n). This is exponential, but it is dramatically better than the O(n!) brute force.

The Assignment Problem

Given n workers and n jobs with a cost matrix, assign each worker to exactly one job to minimise total cost. Bitmask DP works identically — dp[mask] represents assigning the first popcount(mask) workers to the set of jobs in mask.

def assignment(cost):
    n = len(cost)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        worker = bin(mask).count('1')
        if worker >= n:
            continue
        for job in range(n):
            if mask & (1 << job):
                continue
            dp[mask | (1 << job)] = min(
                dp[mask | (1 << job)],
                dp[mask] + cost[worker][job]
            )

    return dp[(1 << n) - 1]

4. Digit DP — Counting Numbers with Properties

Digit DP answers questions like “How many integers in [1, N] have a digit sum divisible by 3?” You process the number digit by digit, tracking whether you are still “tight” (bounded by N) or “free” (already placed a smaller digit).

Template — count numbers up to N with digit sum divisible by K

from functools import lru_cache

def count_divisible_digit_sum(N, K):
    digits = [int(d) for d in str(N)]

    @lru_cache(maxsize=None)
    def dp(pos, remainder, tight, started):
        if pos == len(digits):
            return 1 if started and remainder == 0 else 0

        limit = digits[pos] if tight else 9
        result = 0

        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            new_started = started or (d > 0)
            new_rem = (remainder + d) % K if new_started else 0
            result += dp(pos + 1, new_rem, new_tight, new_started)

        return result

    return dp(0, 0, True, False)

print(count_divisible_digit_sum(100, 3))  # numbers 1..100 with digit sum % 3 == 0

The tight flag is the heart of digit DP. When tight is True, the next digit cannot exceed the corresponding digit of N. Once you place a smaller digit, tight becomes False and all subsequent digits can be 0-9 freely.

Think of it like walking along a tightrope (N’s digits). The moment you step below the rope, you are free to go anywhere.

Common digit DP problems: Count numbers with no repeated digits, count numbers whose digits are non-decreasing, count numbers containing a specific subsequence.

5. DP Optimisation Techniques

Knuth’s Optimisation

For interval DP of the form:

dp[i][j] = min over k in [i, j] of (dp[i][k] + dp[k][j] + C[i][j])

If the cost function C satisfies the quadrangle inequality, the optimal split point opt[i][j] is monotone: opt[i][j-1] {'<'}= opt[i][j] {'<'}= opt[i+1][j]. This narrows the search for k and drops the complexity from O(n^3) to O(n^2).

def knuth_optimised(C, n):
    dp = [[0] * n for _ in range(n)]
    opt = [[0] * n for _ in range(n)]

    for i in range(n):
        opt[i][i] = i

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            lo = opt[i][j - 1] if j - 1 >= i else i
            hi = opt[i + 1][j] if i + 1 <= j else j
            for k in range(lo, hi + 1):
                cost = dp[i][k] + dp[k + 1][j] if k + 1 <= j else dp[i][k]
                cost += C[i][j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    opt[i][j] = k

    return dp[0][n - 1]

Divide and Conquer Optimisation

For 1D DP of the form dp[i] = min over j {'<'} i of (dp[j] + cost(j, i)), if the optimal j for dp[i] is monotonically non-decreasing in i, you can find all optimal j values using divide and conquer in O(n log n) instead of O(n^2).

The idea: solve for the middle element first, then recurse on left and right halves with narrowed search ranges.

def solve(dp_prev, cost, n):
    dp_cur = [float('inf')] * n

    def dc(lo, hi, opt_lo, opt_hi):
        if lo > hi:
            return
        mid = (lo + hi) // 2
        best_k = opt_lo
        for k in range(opt_lo, min(mid, opt_hi + 1)):
            val = dp_prev[k] + cost(k, mid)
            if val < dp_cur[mid]:
                dp_cur[mid] = val
                best_k = k
        dc(lo, mid - 1, opt_lo, best_k)
        dc(mid + 1, hi, best_k, opt_hi)

    dc(0, n - 1, 0, n - 1)
    return dp_cur

6. Profile DP (Broken Profile)

Profile DP handles grid problems where you fill cells column by column (or row by row) and the state captures the “boundary” between the filled and unfilled regions.

Example — tiling a 3 x N grid with 1x2 dominoes

The “profile” is a bitmask of length 3 (the height of the grid) representing which cells in the current column are already filled by horizontal dominoes from the previous column.

from functools import lru_cache

def grid_tiling(n):
    rows = 3

    @lru_cache(maxsize=None)
    def dp(col, mask):
        if col == n:
            return 1 if mask == 0 else 0
        return fill(col, mask, 0)

    @lru_cache(maxsize=None)
    def fill(col, mask, row):
        if row == rows:
            return dp(col + 1, mask)

        if mask & (1 << row):
            # already filled by horizontal domino from previous column
            return fill(col, mask ^ (1 << row), row + 1)

        # Option 1: place horizontal domino into next column
        result = fill(col, mask | (1 << row), row + 1) if col + 1 < n or True else 0
        # Actually: horizontal means this cell + next column same row
        result = 0
        if col + 1 < n:
            result += fill(col, mask | (1 << row), row + 1)

        # Option 2: place vertical domino (this row + next row, same column)
        if row + 1 < rows and not (mask & (1 << (row + 1))):
            result += fill(col, mask, row + 2)

        return result

    return dp(0, 0)

Profile DP is common in competitive programming for grid-based counting problems — tiling, coloring cells with constraints, and “broken profile” variants where some cells are blocked.

Pattern Recognition Cheat Sheet

How to practise

1. Interval DP: Burst Balloons, Strange Printer, Minimum Cost to Merge Stones
2. Tree DP: Sum of Distances in Tree, Distribute Coins in Binary Tree
3. Bitmask DP: Shortest Superstring, Partition to K Equal Sum Subsets, Can I Win
4. Digit DP: Numbers At Most N Given Digit Set, Count Special Integers
5. Optimisations: look for these in competitive programming — Codeforces has many classic problems

Recap

Advanced DP is not about memorising formulas. It is about recognising the shape of the subproblem space:

• Intervals when the subproblem is a contiguous range
• Trees when the structure is hierarchical with parent-child relationships
• Bitmasks when you need to track a subset of a small universe
• Digits when the constraint is on numerical properties of integers
• Optimisations when the brute-force DP is too slow but the optimal split has monotonicity

Master these six patterns and you will handle the vast majority of DP problems that go beyond the classics.

Next steps

For more algorithm patterns, check out Competitive Programming Patterns which covers prefix sums, coordinate compression, meet in the middle, and more techniques that pair beautifully with advanced DP.

Questions or feedback? Email codeloomdevv@gmail.com.