Advanced DP — tips, tricks, and common mistakes

1. Let the constraints pick the shape. Before designing anything, read the bounds: n ≤ 20 ⇒ bitmask; n ≤ 500 with a sequence ⇒ O(n³) interval; two strings ⇒ 2D prefix; "count numbers up to 10¹⁸" ⇒ digit DP; input is a tree ⇒ tree DP. The setter chose those bounds to point at a method.

---

2. Write the state in words first. "solve(l, r) is the best cost for range [l, r]." For multi-dimensional state this discipline matters even more — a vague state is the root of most advanced-DP bugs.

---

3. Default to top-down. Interval DP (fill by length) and bitmask DP (fill by mask value) have non-obvious bottom-up orders; recursion gets them right for free. Only convert when depth or speed forces it.

---

4. Encode sparse state as a map key. When coordinates are large or sparse, swap the array memo for unordered_map<long long,int> with the state packed into one key (i * BIG + j, or the bitmask itself).

---

5. Keep accumulators small in digit DP. The accumulator multiplies the state count. If only divisibility matters, track sum % k, not sum. If only "so far ≤ some cap" matters, clamp it.

---

6. Reuse the LCS/LPS equivalence and similar shortcuts. The longest palindromic subsequence of s is just LCS(s, reverse(s)). Recognising a problem as a relabelled classic saves you from re-deriving a recurrence under time pressure.

---

7. Drop a dimension when one is derivable. In many bitmask assignment problems the position equals __builtin_popcount(mask), so solve(mask) suffices instead of solve(mask, pos) — halving memory and time.

---

8. Test on tiny instances. A 2-character string, a 2×2 distance matrix, a 3-node tree, N = 9 for digit DP. Advanced recurrences fail in small, traceable ways first.

Each dimension multiplies states, and states × work must stay under ~10⁸–10⁹. The classic over-reaches:

• Bitmask beyond ~22. 2ⁿ is 10⁶ at n=20, 10⁷ at n=24, 10⁹ at n=30. If n > ~22, a bitmask over elements won't fit — look for a bitmask over groups, or a different method entirely.
• Interval that's really O(n⁴). solve(l, r) with an O(n) split is O(n³). If your transition itself loops O(n) and you forgot to memoize a sub-result, you can slip to O(n⁴). Keep transition work explicit.
• An accumulator that's secretly huge. Digit DP with acc = the actual number (not a remainder) explodes the table. Always bound the accumulator.
• A third string. solve(i, j, k) over three sequences is O(n³) memory — at n=500 that's 1.25×10⁸ ints ≈ 500 MB. Usually MLE; rethink the state.

Memory, concretely: int memo[1<<20][20] is ~80 M ints ≈ 320 MB — over most limits. Shrink with a smaller type (short/int16), by dropping a dimension, or by noting many masks are unreachable (use a map). Always multiply out states × sizeof(cell) before trusting a global array.

Interval DP

• Base cases i > j (empty) and i == j (single) must be handled before indexing — a split loop on an empty range silently returns garbage.
• The split index runs k from i to j-1; recursing on solve(i, k) and solve(k+1, j) — off-by-one here (solve(k, j)) causes infinite recursion.

Bitmask DP

• 1 << n overflows int for n ≥ 31; use 1u/1LL and a 64-bit mask type when n is large-ish.
• To enumerate submasks of mask, use the idiom for (int sub = mask; sub; sub = (sub - 1) & mask) — a plain for (sub = 0..mask) is both wrong and slow.
• Operator precedence: write (mask & (1 << v)) with parentheses — & binds looser than ==, a notorious silent bug.

Digit DP

• The tight flag is mandatory; without it you'd count numbers above N. It releases (tight && d == limit) only when you place exactly the bound's digit.
• Leading zeros: harmless for digit-sum, but for properties like "number of distinct digits" or "no leading zero" you need a separate started flag.
• Memoize across tight = false states (the bulk); tight = true states form a single path and barely benefit, but including the flag in the state keeps it correct.

Tree DP

• Always pass and skip the parent, or the DFS revisits it and recurses forever.
• Recursion depth equals tree height — O(n) for a path. See the next section.

Tree DP is written as a DFS, and a tree can be a single long path — so the recursion depth can be the full n. With n = 10⁵–10⁶, the default ~1 MB call stack overflows (segfault, not a clean error).

Three fixes, in order of preference:

1. Raise the stack limit (when the judge allows it). On Linux/Codeforces a common trick is to run the solver on a thread with a large stack, or compile with a bigger stack — but this isn't portable.

2. Convert the DFS to an explicit stack / iterative post-order. Push nodes, process children before parents using an explicit stack<int>. More code, but bullet-proof.

3. Process nodes in reverse BFS order. Run a BFS from the root to get an order array; then iterate it backwards so every child is finished before its parent:

This keeps the exact same transition with zero recursion — the safest choice for large trees in a contest.

Bug 1 — memo too small or wrong-shaped. A memo[n][n] for a state that actually ranges to n inclusive needs n+1. Out-of-bounds writes corrupt neighbouring cells and produce baffling wrong answers. Size every dimension to max index + 1.

---

Bug 2 — & precedence in bitmask tests.

---

Bug 3 — forgetting the home leg in TSP. The base case must add dist[u][0] to return to the start; returning 0 solves a path, not a tour.

---

Bug 4 — digit DP without the tight flag (or never releasing it). Drop the flag and you count past N; never release it and you only ever count N itself. The transition must thread tight && (d == limit).

---

Bug 5 — tree DFS revisiting the parent. Omitting the if (v != parent) guard sends the DFS back up the edge it came from → infinite recursion / wrong sums.

---

Bug 6 — integer overflow in counts and costs. Counting DPs (paths, ways, digit DP) overflow int fast; matrix-chain products of large dimensions exceed int too. Use long long, and apply the modulus at every step if asked.

---

Bug 7 — interval base case missing. No if (i >= j) ... guard before the split loop ⇒ the loop body indexes an empty range and recurses without shrinking ⇒ stack overflow.

---

Bug 8 — stale global memo across test cases. A global memo/dp retains the previous test's data. Reset it (or, cleaner, use a local memo sized to the input — and for bitmask tables, only over the reachable mask range).

Run this before you hit submit on an advanced DP:

• Shape matches the constraints (bitmask only if n ≤ ~22, interval only if n ≤ ~500, etc.).
• State defined in one sentence, and every dimension's memo size is max index + 1.
• Base cases handle empty ranges / full masks / last digit / leaves before any indexing.
• Bitmask tests parenthesised, masks 64-bit if n is large, submasks enumerated with the proper idiom.
• Digit DP threads tight correctly and handles leading zeros if the property needs it.
• Tree DFS skips the parent, and depth is safe (iterative/reverse-BFS for n ≥ 10⁵).
• long long for counts/costs; mod everywhere if required.
• Memory states × sizeof(cell) fits; shrink the type or drop a dimension if not.
• Globals reset / memo local between test cases.
• Complexity states × work comfortably under the limit.

Most advanced-DP failures are one of: a memory blow-up from an unbudgeted dimension, a bitmask precedence bug, a missing tight/parent guard, or stack overflow on a deep tree.