Dynamic Programming Advanced

Why this module exists

Basic DP is usually "one index, one recurrence." Advanced DP is about choosing the right state space:

• subsets (bitmasks)
• trees (parent-child constraints)
• intervals (choose last/split point)
• capacity dimensions (knapsack)
• dual-state counting (length + number of ways)

Most failures come from bad state design, not syntax.

Learning goals

By the end, you should be able to:

• derive state from output grain, not from intuition
• choose transition direction that avoids double counting
• map structural constraints (tree, interval, subset) to DP indices
• justify complexity before coding
• debug DP with small invariant checks

A practical DP design loop

Use this loop for every problem:

1. Define what one DP cell means in plain language.
2. Write valid transitions into that cell.
3. Set base cases that make recurrence true at boundaries.
4. Choose iteration order so dependencies are already known.
5. Add one or two invariants to sanity-check intermediate states.

If you cannot clearly explain step 1, you are not ready to code.

Pattern 1: bitmask DP (TSP)

When n is small (n <= ~20), a bitmask can encode visited nodes.

Canonical TSP state:

dp[mask][i] = minimum cost to start at node 0, visit exactly nodes in mask, and end at node i

Transition:

• from (mask, i) to new node j not in mask
• nextMask = mask | (1 << j)
• dp[nextMask][j] = min(dp[nextMask][j], dp[mask][i] + dist[i][j])

Base:

• dp[1<<0][0] = 0

Finish:

• min_i dp[allVisited][i] + dist[i][0]

Complexity:

• O(n^2 * 2^n) time, O(n * 2^n) memory

Pattern 2: DP on trees (take/skip)

For independent-set style constraints on trees ("cannot take adjacent"):

Define two states per node u:

• take[u]: best value in subtree if u is taken
• skip[u]: best value in subtree if u is skipped

Recurrence:

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

Order:

• post-order traversal (children before parent)

Important practical point:

• with n up to 200k, iterative traversal is safer than deep recursion in Go.

Handling negative values:

• skip allows "take nothing" behavior, so global result can still be 0.

Pattern 3: interval DP (burst balloons)

In interval DP, you usually choose the last action inside an interval.

For burst balloons:

• add sentinels: vals = [1] + nums + [1]
• use open interval state:
  • dp[l][r] = best coins from bursting balloons strictly between l and r

Transition:

• choose k as last balloon in (l, r)
• dp[l][r] = max(dp[l][k] + dp[k][r] + vals[l]*vals[k]*vals[r])

Order:

• increase interval length, so smaller intervals are solved first

Complexity:

• O(n^3) time, O(n^2) memory

Pattern 4: 0/1 knapsack (backward capacity)

State:

• dp[c] = best value achievable with capacity c after processing some prefix

For each item (w, v):

• iterate c from capacity down to w
• dp[c] = max(dp[c], dp[c-w] + v)

Why backward?

• prevents reusing the same item multiple times in one iteration

Forward iteration changes semantics to unbounded knapsack.

Pattern 5: count LIS (length + ways)

Need both:

• length[i]: LIS length ending at i
• count[i]: number of LIS of that length ending at i

Initialize:

• length[i] = 1
• count[i] = 1

Transition for each j < i with nums[j] < nums[i]:

• if length[j] + 1 > length[i]:
  • better length found
  • update length and replace count
• else if equal:
  • add counts (count[i] += count[j])

Final answer:

• sum count[i] for all i where length[i] equals global max length

Complexity:

• O(n^2) time, O(n) memory

Choosing the right pattern quickly

Ask:

1. Is "which elements already chosen" the core state?
   • yes -> bitmask DP
2. Is the input a tree and constraints are local on edges?
   • yes -> tree DP
3. Does score depend on neighbors after removals/splits?
   • yes -> interval DP
4. Is there a capacity/budget dimension with include/exclude choice?
   • yes -> knapsack
5. Are you asked for number of optimal subsequences?
   • yes -> length + count DP

Debugging checklist by pattern

Bitmask DP:

• dp[1<<0][0] initialized?
• transitions only to unvisited nodes?
• final return includes edge back to start?

Tree DP:

• parent edge excluded in child loops?
• post-order truly processes children first?
• final answer is max(take[root], skip[root])?

Interval DP:

• sentinels added correctly?
• interval is open (l, r)?
• iteration by increasing interval length?

Knapsack:

• capacity loop direction is backward?
• base dp starts at zeros?
• w > capacity items naturally ignored?

Count LIS:

• strict <, not <=?
• count replaced on better length, added on equal length?
• empty input returns 0?

What you will build in this module

• tsp-bitmask: subset DP with endpoint state
• tree-robber: tree DP with take/skip
• burst-balloons: interval DP with last-burst choice
• knapsack-01: backward 1D capacity DP
• lis-count: dual-state DP for optimal length and count

Focus on writing state meaning in one sentence before coding each solution.