Dynamic Programming — tips, tricks, and common mistakes

1. Write the recurrence in words before code. Say out loud: "solve(state) is the [answer] for [what], and it equals [combination of smaller calls]." If you can't say it cleanly, your state is wrong — fixing it on paper is far cheaper than debugging.

---

2. Default to top-down (recursion + memo). It follows your reasoning directly, so it's the fastest route from "I understand the recurrence" to working code. Convert to bottom-up only when you need raw speed, stack safety, or a rolling-array space trick.

---

3. Use a sentinel that can't be a real answer to mark 'not computed'.

If -1 is a valid answer (e.g. min-coins where 0 is valid, or signed sums), use a different sentinel or a separate seen[] boolean.

---

4. memset(arr, -1, ...) and memset(arr, 0, ...) work; memset(arr, x, ...) does not for general x. memset sets bytes, so only 0, -1 (all bits 1), and a few others behave as expected. To fill a memo with a custom sentinel, use fill / fill_n or a loop.

---

5. Prefer arrays over unordered_map when the state is bounded ints. A 2D array indexed by (i, j) is dramatically faster than hashing a pair. Reserve maps for sparse or non-integer states.

---

6. Minimise the state. Every extra parameter multiplies the memo size and the work. Before coding, ask whether the answer truly depends on a parameter or only on a summary of it — knapsack needs (index, remaining capacity), not the exact set chosen. Fewer dimensions = smaller memo = faster.

---

7. Call solve on the right starting state and read the right result. Decide up front whether the answer is solve(0, W), solve(0), or max over i of solve(i). Many WA submissions are correct recurrences invoked or aggregated wrongly.

---

8. Sanity-check by hand on n = 1, 2, 3. Trace the first few calls manually and compare to your code's output. Tiny cases expose base-case and off-by-one bugs instantly.

In top-down DP you never manage a fill order — the recursion fetches each dependency on demand and the memo guarantees each state is solved once. What you do have to get right is the structure of the recursive call: which sub-state each branch recurses into.

The take/skip distinction — the most famous one (knapsack family):

Recursing on i+1 retires the item after one use; recursing on i keeps it available. That single index is the difference between the two problems. (In bottom-up the same distinction appears as iterating capacity downward for 0/1 vs. upward for unbounded — same idea, easier to get backwards.)

The combination-vs-permutation distinction (coin-change counting): keep a coin index in the state. ways(i, x) with skip → ways(i+1, x) and take → ways(i, x - c[i]) counts each combination once. Drop the index — ways(x) = Σ ways(x - c) — and you count ordered permutations instead (1+2 and 2+1 separately).

Always reduce toward a base case. Every branch must move to a strictly smaller sub-state (smaller i, smaller cap, smaller x); otherwise the recursion never terminates and the stack overflows.

Bug 1 — wrong or missing base case. The recurrence is right but the base (i == n, cap == 0, x == 0) is unset or wrong, so everything built on it is off.

Catch it: evaluate the smallest calls by hand and assert them. Most DP WAs are base-case bugs.

---

Bug 2 — Kadane mistakes. Two classics: seeding the base as 0 instead of a[0] (returns 0 for all-negative input when the subarray must be non-empty), and returning best(n-1) instead of max over all best(i).

---

Bug 3 — wrong recursion index in knapsack's take branch. Recursing on i when the item is single-use turns 0/1 into unbounded (item reused) → overcounts value. 0/1 must recurse on i+1.

---

Bug 4 — counting coin combinations without a coin index. ways(x) = Σ_c ways(x - c) counts permutations (1+2 ≠ 2+1). Put the coin index in the state — ways(i, x) with take → ways(i, …), skip → ways(i+1, …) — to count combinations.

---

Bug 5 — integer overflow. Counting DPs explode fast; sums of values can exceed int (>2.1×10⁹).

If the problem says "answer modulo 10⁹+7," take the mod at every addition/multiplication inside the recursion, not just at the end.

---

Bug 6 — stale memo between test cases. A global memo carries answers from the previous test into the next.

If you must use a global memo for speed, memset (or reset just the touched cells) at the start of every test.

---

Bug 7 — calling solve on the wrong start, or reading the wrong result. Returning solve(n-1) when the answer is solve(0) or max over i of solve(i). Re-derive which call corresponds to the original problem.

---

Bug 8 — indexing before the base-case guard. Touching a[i] or computing cap - w[i] before checking bounds.

MLE (memory limit exceeded): in top-down, the memo dominates.

• A memo[1005][1005] of int is ~4 MB (fine); a memo[5005][5005] is ~100 MB (risky), and long long doubles it. Shrink it by minimising state dimensions first.
• Prefer a flat vector<int> memo(rows*cols) indexed i*cols + j over vector<vector<int>> for tight memory and better cache behaviour.
• When the memo simply won't fit and each layer depends only on the previous, bottom-up with a rolling array (two rows, or one) is the fix — a case where converting away from recursion pays off.

TLE (time limit exceeded):

• Re-estimate states × work-per-call. If it exceeds ~10⁸–10⁹, the state is too big or the transition too slow.
• unordered_map memo keys are slow from hashing — switch to plain array/vector indexing.
• Recomputing a min/max/sum over a range inside the transition hides an extra O(n) factor; precompute prefix sums or maintain a running value.
• A giant global memo memset every test case is a sneaky TLE — reset only the cells you used, or use a local memo sized to the input.

Stack overflow — top-down's real risk. Recursion depth ≈ the longest dependency chain; for linear DP that's n. Near n ≈ 10⁵–10⁶, the call stack (often ~1 MB) overflows. Convert that DP to bottom-up iteration, which uses no recursion.

When a problem smells like DP but the recurrence isn't obvious, follow this mechanical pipeline — it almost never fails, and it's exactly how the top-down solutions in this chapter were built:

1. Write the brute-force recursion. Ignore efficiency. Just express "make a choice, recurse on the rest." Get it correct on small inputs.

2. Identify the state. The arguments to your recursive function that actually affect the result are the DP state. Drop any argument the answer doesn't depend on.

3. Add memoization. Cache by state. You now have a working, efficient top-down DP — usually enough to get AC.

4. (Optional) Tabulate. Rewrite as an iterative table fill only if you need more speed, stack safety, or a space optimisation.

Worked example — partition into two equal-sum halves (subset sum to total/2):

The recursion is the recurrence; the memo is the DP table. Internalising this pipeline means you can derive most rudimentary DPs from scratch under contest pressure — stop at step 3 unless something forces step 4.

Run this before you hit submit:

• State defined precisely — you can state in words what solve(state) means.
• Base cases return immediately and are verified by hand (i == n, cap == 0, x == 0).
• Every branch shrinks the state toward a base case (the recursion terminates).
• Transition index correct — take → i+1 for 0/1, i for unbounded; coin index present for combinations.
• Guards precede indexing (i >= n before a[i], w[i] <= cap before cap - w[i]).
• long long where counts/sums can overflow; mod applied everywhere if required.
• Memo fresh per test case — prefer a local memo; reset a global one.
• Right start / right result — solve(0, …) or max over i of solve(i) as the problem demands.
• Complexity (states × work) under the limit, and depth safe from stack overflow.

Most DP submissions that fail trip exactly one of these — the base case, the take-branch index, or overflow.