Dynamic Programming Advanced

Why this module exists

Basic DP covers 1D arrays. Advanced DP requires modeling state carefully and choosing the right transitions: subsets, trees, intervals, and knapsack.

Bitmask DP (subset DP)

When n is small (<= 20), a bitmask encodes which items are chosen.

State example: dp[mask][i] = min cost to reach i after visiting nodes in mask

Time: O(n^2 * 2^n). Great for TSP-like problems.

DP on trees

Tree structure removes cycles. Use post-order traversal.

Common pattern (take / skip):

• take[u] = value[u] + sum(skip[child])
• skip[u] = sum(max(take[child], skip[child]))

Interval DP

Interval DP chooses a split point inside a range.

Example (burst balloons): dp[l][r] = max over k in (l..r) of dp[l][k] + dp[k][r] + score(l,k,r)

Time: O(n^3)

Knapsack variants

• 0/1 knapsack: each item once, iterate capacity backwards
• Unbounded: iterate capacity forwards
• Subset sum / partition are special cases

LIS variants

• Length (basic)
• Count number of LIS (DP)
• Recover sequence
• Envelopes after sorting (LIS on one dimension)

What you will build

• Bitmask TSP (small n).
• Tree DP (no-adjacent constraint).
• Interval DP (burst balloons).
• 0/1 knapsack.
• Count of longest increasing subsequences.