Advanced DP: Bitmask, Intervals, Digit DP

Concept

Bitmask DP: the state includes a bitmask of which items are used — ideal when n ≤ 20 (e.g. Travelling Salesman in O(n² · 2ⁿ)).

Interval DP: dp[i][j] = best answer for the sub-range i..j, built from smaller intervals (Burst Balloons, Matrix Chain Multiplication).

Digit DP counts numbers up to N with a property by walking digits with a 'tight' flag. DP on trees combines children's answers in a post-order DFS.

Complexity

Code (Python)

from functools import lru_cache

def tsp(dist):
    n = len(dist)
    @lru_cache(None)
    def go(mask, u):
        if mask == (1 << n) - 1:
            return dist[u][0]
        best = float("inf")
        for v in range(n):
            if not mask & (1 << v):
                best = min(best, dist[u][v] + go(mask | (1 << v), v))
        return best
    return go(1, 0)

def max_coins(nums):                 # Burst Balloons (interval DP)
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for l in range(n - length):
            r = l + length
            for k in range(l + 1, r):
                dp[l][r] = max(dp[l][r], a[l] * a[k] * a[r] + dp[l][k] + dp[k][r])
    return dp[0][n - 1]

Remember

• n ≤ 20 and 'visit all' → bitmask.
• 'Last operation splits range' → interval DP.
• Define the state in words before writing code.