Dynamic Programming

Dynamic Programming has a reputation for being hard. It really isn't — it's just recursion that remembers what it already computed. Every DP problem you'll ever see is one of about eight templates, and once you can identify which template fits, the rest is bookkeeping. The hard part is recognising the pattern, not coding it.

What DP Actually Is

Two ingredients are required, both:

1. Optimal substructure — the optimal answer to the whole problem can be built from optimal answers to smaller subproblems. 2. Overlapping subproblems — the same subproblems appear over and over in the naive recursion.

If both hold, *cache the subproblem answers* and you've turned exponential work into polynomial work.

` fib(5) ├── fib(4) │ ├── fib(3) ← computed twice without memo │ │ ├── fib(2) ← computed FIVE times │ │ └── fib(1) │ └── fib(2) └── fib(3) ← already computed ├── fib(2) └── fib(1) `

Memoise once → each subproblem runs once → O(n) instead of O(2ⁿ).

Daily Mental Model: Cached Road Trip

You're planning a trip from city A → … → city Z. To find the cheapest route to Z, you need the cheapest route to every city that connects directly into Z. Once you compute "cheapest to Y", you don't recompute it the next time it shows up — you look it up. That cache is the entire DP idea.

Beginner Mistakes to Skip

1. Not memoising overlapping subproblems. Naive recursive Fibonacci is O(2ⁿ) — and slow at n = 35. The same recursion *with a cache* is O(n). 2. Wrong base case. \fib(0) = 0, fib(1) = 1\. Many DPs are off-by-one (\dp[0]\ represents "nothing chosen"). Always trace base cases by hand for n = 0 and n = 1. 3. Wrong iteration order in tabulation. \dp[i]\ depends on \dp[i−1]\ → fill left to right. \dp[i][j]\ depends on \dp[i−1][j]\ and \dp[i][j−1]\ → fill top-to-bottom, left-to-right. 4. Not caching before return in memoisation. \return memo[n] = recurse(...)\ — the assign happens before the return. Forgetting it makes the cache useless. 5. Off-by-one in 0/1 vs unbounded knapsack iteration direction. 0/1: iterate capacity from W down to w[i] (otherwise you reuse an item). Unbounded: iterate forward (you *want* reuse). 6. Building the full table when a single row suffices. If \dp[i]\ only uses \dp[i−1]\, drop the table to two rows and save a factor of n in space.

Intermediate: Top-Down vs Bottom-Up — Both Code Up Front

Top-down (memoisation) — recurse from the answer, cache subproblem results:

`js function fibMemo(n, memo = {}) { if (n <= 1) return n; if (memo[n] !== undefined) return memo[n]; return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); } `

Bottom-up (tabulation) — fill a table from the base cases up:

`js function fibTab(n) { if (n <= 1) return n; const dp = [0, 1]; for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n]; } `

Space-optimised — only the last two values matter:

`js function fibO1(n) { let a = 0, b = 1; for (let i = 2; i <= n; i++) [a, b] = [b, a + b]; return n ? b : a; } `

Aspect	Top-down	Bottom-up
Direction	answer → base cases	base cases → answer
Solves only needed subproblems	✅	❌ (computes all)
Stack overflow risk	yes	no
Easier to space-optimise	no	✅
Easier to write first	usually ✅	sometimes

The standard workflow: write naive recursion → add memoisation → convert to tabulation → space-optimise. Each step is mechanical.

Intermediate: The 5-Step DP Process

1. Define the state. What's the smallest set of variables that uniquely identifies a subproblem? Usually a tuple (index, capacity, mask, …). 2. Write the recurrence. Express \dp[state]\ in terms of *smaller* states. 3. List base cases. Smallest states with a known answer. 4. Pick computation order. For tabulation, ensure each dependency is filled first. 5. Optimise space. Drop dimensions you don't need.

This explicit process turns "I have no idea where to start" into a checklist.

Intermediate: 1D Linear DP

State is a single index \i\.

• Climbing stairs: \dp[i] = dp[i-1] + dp[i-2]\ (Fibonacci).
• House robber: \dp[i] = max(dp[i-1], dp[i-2] + nums[i])\ — choose to skip or rob.
• Kadane's max-subarray: \dp[i] = max(nums[i], dp[i-1] + nums[i])\. The answer is \max(dp)\. O(n), one variable suffices.
• Decode ways: count partitions of a digit string into valid letter codes.

Intermediate: 2D Grid / Two-Sequence DP

State is a pair (row, col) or (i, j) over two strings.

• Unique paths: \dp[i][j] = dp[i-1][j] + dp[i][j-1]\.
• Min path sum: \dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])\.
• Longest Common Subsequence (LCS):

` if s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) `

• Edit distance (Levenshtein):

` dp[i][j] = min( dp[i-1][j] + 1, // delete dp[i][j-1] + 1, // insert dp[i-1][j-1] + (s1[i] != s2[j]) // replace or match ) `

Advanced: Knapsack — and the Iteration-Direction Trick

0/1 Knapsack (each item used 0 or 1 times):

`js for (let i = 0; i < n; i++) for (let w = W; w >= wt[i]; w--) // REVERSE — prevents reuse dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]); `

Unbounded Knapsack (each item used unlimited times):

`js for (let i = 0; i < n; i++) for (let w = wt[i]; w <= W; w++) // FORWARD — allows reuse dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]); `

The *only* difference is the iteration direction of the inner loop. Subset Sum, Coin Change, and Target Sum are all knapsack variants.

Advanced: Interval DP

Subproblems are defined over a contiguous interval \[i, j]\. Standard pattern: enumerate length first, then start, then a split point k.

`js for (let len = 2; len <= n; len++) for (let i = 0; i + len <= n; i++) { const j = i + len - 1; for (let k = i; k < j; k++) dp[i][j] = Math.max(dp[i][j], something(dp[i][k], dp[k+1][j])); } `

Examples: Matrix chain multiplication, Burst balloons, Palindrome partitioning (min cuts).

Advanced: Bitmask DP — Brute Force Over Subsets, Memoised

When n ≤ ~20, you can encode "which elements have I used" as a bitmask of n bits.

TSP (Travelling Salesman):

` dp[mask][i] = minimum cost path that visits exactly the cities in mask, ending at city i dp[mask

(1<

(1<`

States: \2ⁿ × n\. Transitions: O(n). Total O(2ⁿ · n²). For n = 20, that's ~400M operations — fits in a few seconds. The brute-force O(n!) is utterly hopeless at n = 20 (~10¹⁸).

Advanced: Tree DP

DP on tree nodes via post-order DFS — children's answers feed the parent's answer.

• House Robber III: each node returns \(rob, notRob)\. Parent's \rob\ = node.val + child.notRob. Parent's \notRob\ = max(child.rob, child.notRob).
• Tree diameter: longest path between any two nodes — for each node, the longest path passing through it = (max depth on left) + (max depth on right).
• Binary Tree Cameras: state = (covered, has-camera, uncovered) per node.

Advanced: Digit DP — Counting Valid Numbers in [1, N]

Process digits left to right with state \dp[pos][tight][...]\ where \tight\ says "still bounded by N's prefix". Use cases: count numbers in [L, R] with no equal adjacent digits, count numbers whose digit sum is divisible by k, count numbers without 4s.

Advanced: How to Recognise a DP Problem

Problem says	Probably DP
"minimum / maximum cost / value"	yes
"number of ways to …"	yes (counting DP)
"is it possible to make sum K?"	yes (subset sum)
"longest / shortest subsequence"	yes
"you can make choices at each step"	yes
n ≤ 20	bitmask DP
n ≤ 100	possibly O(n³) interval DP
n ≤ 1000	O(n²) DP
n ≤ 10⁶	O(n) DP

Advanced: Common Pitfalls When Debugging DP

1. Initial values matter — for max problems initialise to −∞, for min to +∞, for counting to 0. 2. Don't memoise on a state that doesn't actually distinguish subproblems. Symptom: cache-key collisions producing wrong answers. 3. Don't memoise on a state that includes the answer you're computing. Symptom: cache misses everywhere → no speedup. 4. Verify recurrence on n = 1, 2, 3 by hand.

Practice Path

1. Write Fibonacci three ways: naive recursion, top-down memoised, bottom-up tabulated. Compare runtimes for n = 35. 2. Solve 0/1 Knapsack with a 2D table, then space-optimise to a 1D array iterating capacity in reverse. 3. Solve Edit Distance between two strings with a 2D DP table. 4. Solve Longest Increasing Subsequence (LIS) in O(n²) DP first, then in O(n log n) with patience sort + binary search.