Dynamic Programming Advanced

Goal:

• choose correct state space
• enforce transition order
• avoid double counting

Patterns in this module

• bitmask DP (TSP)
• tree DP (take/skip)
• interval DP (burst balloons)
• 0/1 knapsack
• count LIS (length + ways)

DP Design Loop

1. define one-cell meaning
2. define transition
3. define base case
4. choose safe iteration order
5. add invariant checks

Bitmask DP (TSP)

• state: dp[mask][i]
• base: dp[1<<0][0] = 0
• transition: go to unvisited j
• finish: add return edge to 0
• complexity: O(n^2 * 2^n)

Tree DP (Independent Set)

• take[u] = value[u] + sum(skip[child])
• skip[u] = sum(max(take[child], skip[child]))
• post-order traversal required
• answer: max(take[root], skip[root])

Interval DP (Burst Balloons)

• pad with sentinels: [1] + nums + [1]
• state: dp[l][r] on open interval (l, r)
• choose last burst k in (l, r)
• complexity: O(n^3)

Knapsack

• 0/1 knapsack: capacity loop backward
• forward loop changes semantics to unbounded
• 1D DP enough for value maximization

Count LIS

• length[i]: best length ending at i
• count[i]: number of ways for that length
• strict increase uses <
• replace count on better length, add on tie

Common Bugs

• state meaning unclear
• wrong loop order
• off-by-one interval bounds
• duplicate counting in LIS
• reusing item in 0/1 knapsack due forward loop