Advanced DP — theory and understanding

In Part 1 the state was almost always one number — an index i, a capacity c, an amount x. That's enough for problems over a single sequence with a local choice.

Many contest problems aren't like that. The answer for a subproblem depends on more than one coordinate:

• Comparing two sequences at once (LCS, edit distance) → state is a pair (i, j).
• Solving a contiguous range and choosing where to split it (matrix chain, palindromes) → state is an interval (l, r).
• Tracking which elements have been used when order is unconstrained (TSP, assignment) → state is a subset, encoded as a bitmask.
• Building a number digit by digit under an upper bound (counting problems) → state is (position, accumulated value, flags).
• Aggregating answers up a tree → state is a node (plus a small status).

The single most important realisation for Part 2: the recipe does not change. You still (1) define the state, (2) write the transition as choices recursing on smaller states, (3) set base cases, and (4) memoize. The only new skill is recognising what the state should be when one index won't do.

Almost every intermediate DP you'll meet fits one of these moulds. Memorise the state signature of each — recognising it is most of the work.

Shape	State	Transition idea	Typical size
2D prefix	solve(i, j) over two sequences	match/skip a character from each	O(n·m)
Interval	solve(l, r) over a range	pick a split point or an endpoint	O(n²) states, O(n) work
Bitmask	solve(mask, i) — mask = used set	add one unused element	O(2ⁿ·n)
Digit	solve(pos, acc, tight)	choose the next digit 0..limit	O(digits·acc·2)
Tree	solve(node, status) via DFS	combine children's answers	O(nodes)

Notice the pattern: the state changes from problem to problem, but each transition is still "enumerate the choices available here, recurse on the resulting smaller state, combine." If you can name the shape, you can usually write the code in minutes.

The Part 1 mantra still rules everything:

Total time ≈ (number of distinct states) × (work per transition).

Extra dimensions multiply the state count, so they decide feasibility. Read the constraints and back-calculate before writing code.

• 2D prefix: n·m states. With n, m ≤ 5000 that's 2.5×10⁷ — fine.
• Interval: n² states, each doing O(n) work to try every split → O(n³). So n ≤ 500 roughly.
• Bitmask: 2ⁿ subsets (times n for a position) → only viable for n ≤ ~20. At n = 20, 2²⁰·20 ≈ 2×10⁷; at n = 24 it's already ~4×10⁸.
• Digit: (#digits) × (range of accumulator) × 2. Tiny — digit DP runs in microseconds; the accumulator range is the only thing to watch.
• Tree: one (or a few) states per node → O(n) or O(n · status).

The tell-tale clue in the statement: the constraints announce the intended shape. n ≤ 20 screams bitmask. n ≤ 500 with a sequence hints O(n³) interval DP. A bound given as a 10¹⁸ number you must count up to screams digit DP. Train yourself to read constraints as hints.

Nothing about caching changes — the memo just gains dimensions matching the state.

When the state doesn't fit a dense array — coordinates too large or sparse (e.g. values up to 10⁹) — switch the cache to a hash map keyed by the state:

Use a dense array whenever the state is small bounded integers (far faster); reserve maps for genuinely sparse state spaces. Tree DP is the one shape that usually skips an explicit memo array entirely: a single DFS visits each node once, so the recursion is the memoization — store each node's answer in a dp[node] array as you return from its DFS call.

Bottom-up tabulation requires you to fill states in an order where every dependency is ready first. For Part 1's linear DP that order was obvious (left to right). For Part 2 shapes it is not:

• Interval DP must be filled by increasing interval length, not by l then r — get it wrong and you read empty cells.
• Bitmask DP must be filled by increasing mask value (so subsets come before supersets), which works only because mask & (mask-1) < mask.
• Digit / tree DP have no natural array order at all.

Top-down recursion sidesteps every one of these. You write the transition; the call stack pulls each dependency exactly when needed and the memo ensures it's computed once. That's why memoized recursion is the default for Part 2 — the harder the fill order, the bigger the win. You convert to bottom-up only when recursion depth threatens the stack (deep trees, long sequences) or you need the last bit of speed.

The mental model to carry forward: advanced DP is Part 1's recipe with a bigger state. Identify the shape, write the recursive transition, add a memo with the right number of dimensions, and let recursion handle the order.