Chapter 13 — Dynamic Programming

Connect Backward

Chapter 4a introduced Fibonacci with memoization and called it "the gateway to DP." Here's what that meant:

// Naive recursion — exponential
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);  // computes fib(3) many times
}

// With memoization — linear
const memo = {};
function fib(n) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1) + fib(n - 2);
  return memo[n];
}

The problem with naive Fibonacci is that fib(3) is computed exponentially many times. Memoization caches the result after the first computation. This is dynamic programming: don't solve the same subproblem twice.

Chapter 12 showed that every graph traversal is O(V + E) because each vertex and edge is visited exactly once. DP achieves polynomial time for the same reason: each subproblem is solved exactly once, then cached.

Chapter 12's topological sort is directly connected to DP. Bottom-up DP fills in a table in topological order of the subproblem DAG. When you compute dp[i] from dp[i-1] and dp[i-2], you're doing a topological traversal of the implicit DAG where i depends on i-1 and i-2.

1. The Two Ingredients

A problem is solvable with DP if and only if it has:

Optimal Substructure

The optimal solution to the problem can be built from optimal solutions to subproblems.

Example: Shortest path from A to C through B. If the shortest path is A→B→C, then A→B must be the shortest path from A to B, and B→C must be the shortest path from B to C. If either segment were suboptimal, you could replace it and get a shorter total path. This is optimal substructure.

Counterexample: Longest simple path (can't revisit nodes). The longest path from A to C might not contain the longest path from A to B — because taking a longer path to B might leave fewer nodes available for B to C.

Overlapping Subproblems

The same subproblems appear multiple times.

Fibonacci: fib(5) requires fib(4) and fib(3). fib(4) requires fib(3) and fib(2). fib(3) is needed twice. Without caching, this explodes exponentially.

When subproblems don't overlap: Divide and conquer (merge sort, quick sort) — each subproblem is independent. No need to cache. DP is overkill for non-overlapping subproblems.

2. The Two Approaches

Top-Down: Memoization (Recursion + Cache)

Write the recursive solution naturally. Add a cache (Map or array). Before computing, check if the answer is cached. After computing, store it.

function solve(n, memo = new Map()) {
  if (isBaseCase(n)) return baseAnswer(n);
  if (memo.has(n)) return memo.get(n);
  
  const result = /* recurse on subproblems */;
  memo.set(n, result);
  return result;
}

Pros: Natural to write (direct translation of the recurrence). Only solves subproblems that are actually needed (lazy).
Cons: Recursion overhead. Risk of call stack overflow for large n.

Bottom-Up: Tabulation (Iterative + Table)

Identify the order in which subproblems must be solved (topological order of the subproblem DAG). Fill a table from smallest subproblems up to the answer.

function solve(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = baseCase0;
  dp[1] = baseCase1;
  
  for (let i = 2; i <= n; i++) {
    dp[i] = /* combine dp[i-1], dp[i-2], ... */;
  }
  
  return dp[n];
}

Pros: No recursion overhead. Easy to optimize space (often only need last few values).
Cons: Must figure out the traversal order. Computes all subproblems even if some aren't needed.

Which to use? Both give the same result. Top-down is easier to derive (write recursion, add memo). Bottom-up is often faster in practice. For interviews, start with top-down to establish correctness, then convert to bottom-up if asked to optimize.

3. The Four-Step DP Framework

Every DP problem follows this process:

1. Define the state. What does dp[i] (or dp[i][j]) represent? Write it out in words.
2. Write the recurrence. How does dp[i] relate to smaller subproblems?
3. Identify base cases. The smallest subproblems where the answer is known directly.
4. Determine traversal order. Bottom-up: ensure each dp[i] is computed after all subproblems it depends on.

Let's apply this to Fibonacci:

1. State: dp[i] = the i-th Fibonacci number.
2. Recurrence: dp[i] = dp[i-1] + dp[i-2].
3. Base cases: dp[0] = 0, dp[1] = 1.
4. Order: Left to right (i = 2, 3, ..., n). Each dp[i] depends on dp[i-1] and dp[i-2], both already computed.

4. 1D DP

Climbing Stairs

n stairs. Each step you can climb 1 or 2 stairs. How many distinct ways to reach the top?

State: dp[i] = number of ways to reach stair i.
Recurrence: To reach stair i, you came from stair i-1 (1 step) or stair i-2 (2 steps). So dp[i] = dp[i-1] + dp[i-2].
Base cases: dp[1] = 1 (one way: single step), dp[2] = 2 (two ways: 1+1, or 2).
This is exactly Fibonacci.

function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    [prev2, prev1] = [prev1, prev1 + prev2];
  }
  return prev1;
}

Space optimized: instead of storing the full array, only the last two values are needed. dp[i] only depends on dp[i-1] and dp[i-2].

House Robber

Array of house values. Adjacent houses have a security system — can't rob two adjacent houses. Maximize total robbed amount.

What do I have? nums = [2, 7, 9, 3, 1].
What do I want? Maximum sum with no two adjacent elements.
Why DP? At each house, you decide to rob or skip. The optimal decision depends on what you did at the previous house — overlapping subproblems.

State: dp[i] = maximum money robbed from houses 0..i.
Recurrence: At house i, either:

• Rob house i: can't rob i-1, so dp[i-2] + nums[i]
• Skip house i: dp[i-1] Take the max: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
  Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

function rob(nums) {
  if (nums.length === 1) return nums[0];
  
  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1]);
  
  for (let i = 2; i < nums.length; i++) {
    const curr = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = curr;
  }
  
  return prev1;
}

Dry run on [2, 7, 9, 3, 1]:

i=0: prev2=2
i=1: prev1=max(2,7)=7
i=2: curr=max(7, 2+9)=max(7,11)=11. prev2=7, prev1=11
i=3: curr=max(11, 7+3)=max(11,10)=11. prev2=11, prev1=11
i=4: curr=max(11, 11+1)=max(11,12)=12. prev2=11, prev1=12

Result: 12 (rob houses 0,2,4: 2+9+1=12). ✓

5. Unbounded Knapsack — Coin Change

Given coins [1, 5, 11] and amount 15, find minimum number of coins to make amount. Each coin can be used unlimited times.

Why DP? Greedy fails here. With coins [1,5,11] and amount 15: greedy picks 11, then 4×1 = 5 coins. Optimal is 3×5 = 3 coins.

State: dp[i] = minimum coins to make amount i.
Recurrence: For each coin c where c <= i: dp[i] = min(dp[i], dp[i-c] + 1). Try every coin; the best option gives one more coin than making i-c.
Base cases: dp[0] = 0 (zero coins to make amount 0). dp[i] = Infinity initially (can't make this amount yet).
Order: i = 1, 2, ..., amount.

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Full dry run on coins=[1,5,11], amount=15:

dp[0]=0, dp[1..15]=Infinity

i=1: coin 1: dp[0]+1=1 → dp[1]=1
     coin 5: 5>1, skip
     coin 11: 11>1, skip
i=2: coin 1: dp[1]+1=2 → dp[2]=2
i=3: dp[3]=3
i=4: dp[4]=4
i=5: coin 1: dp[4]+1=5
     coin 5: dp[0]+1=1 → dp[5]=1
i=6: coin 1: dp[5]+1=2. coin 5: dp[1]+1=2 → dp[6]=2
i=7: dp[6]+1=3. dp[2]+1=3 → dp[7]=3
i=8: dp[8]=4 (via 5+1+1+1, or 1×8)
i=9: dp[9]=4 (5+1+1+1+1, but also 1×9)
     Wait: dp[4]+1=5, dp[9-5=4]+1=5. coin 1: dp[8]+1=5. So dp[9]=5
     Hmm. Let me recount: 5+1+1+1+1=5 coins? No: that's 5, then 1,1,1,1 = 5 coins for amount 9. Or 1×9=9 coins. Best is 5+4×1=5 coins.
     Wait, we can also do: is there a better way? With [1,5,11]: 9 = 5+4 = 5+1+1+1+1 = 5 coins. Or 1×9=9. dp[9]=5? Let me recheck by filling table:
     dp[6]=2 (5+1), dp[7]=3 (5+1+1), dp[8]=4, dp[9]=5, dp[10]=2 (5+5)
i=10: coin 5: dp[5]+1=2 → dp[10]=2
i=11: coin 1: dp[10]+1=3. coin 5: dp[6]+1=3. coin 11: dp[0]+1=1 → dp[11]=1
i=12: coin 1: dp[11]+1=2. coin 5: dp[7]+1=4. coin 11: dp[1]+1=2 → dp[12]=2
i=13: coin 1: dp[12]+1=3. coin 11: dp[2]+1=3 → dp[13]=3
i=14: coin 1: dp[13]+1=4. coin 5: dp[9]+1=6. coin 11: dp[3]+1=4 → dp[14]=4
i=15: coin 1: dp[14]+1=5. coin 5: dp[10]+1=3. coin 11: dp[4]+1=5 → dp[15]=3

Result: dp[15] = 3 (three 5-coins). ✓ Greedy would have given 5 coins.

Time: O(amount × |coins|). Space: O(amount).

6. 2D DP — Longest Common Subsequence

Given text1 = "abcde", text2 = "ace", find the length of the longest common subsequence (LCS). A subsequence preserves relative order but need not be contiguous.

LCS is the foundation for git diff and file comparison.

State: dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1].
Recurrence:

• If text1[i-1] === text2[j-1]: this character is in the LCS. dp[i][j] = dp[i-1][j-1] + 1.
• Else: skip one character from either string. dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  Base cases: dp[0][j] = 0 and dp[i][0] = 0 — LCS with empty string is 0.

function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  
  return dp[m][n];
}

Full table for "abcde" vs "ace":

      ""  a  c  e
  ""  [0, 0, 0, 0]
  a   [0, 1, 1, 1]
  b   [0, 1, 1, 1]
  c   [0, 1, 2, 2]
  d   [0, 1, 2, 2]
  e   [0, 1, 2, 3]

Read cell by cell:

• dp[1][1]: text1[0]='a' === text2[0]='a' → dp[0][0]+1 = 1
• dp[1][2]: text1[0]='a' ≠ text2[1]='c' → max(dp[0][2], dp[1][1]) = max(0,1) = 1
• dp[2][1]: text1[1]='b' ≠ text2[0]='a' → max(dp[1][1], dp[2][0]) = max(1,0) = 1
• dp[3][2]: text1[2]='c' === text2[1]='c' → dp[2][1]+1 = 2
• dp[5][3]: text1[4]='e' === text2[2]='e' → dp[4][2]+1 = 2+1 = 3 ✓

Result: 3 ("ace"). ✓

Space optimization: Each row only depends on the previous row. Reduce to O(n) space using two rolling arrays, or even O(n) with one array processed in the right direction.

7. Edit Distance — Levenshtein Distance

Given word1 = "horse" and word2 = "ros", find minimum operations (insert, delete, replace) to convert word1 to word2.

This is the algorithm behind spell checkers, DNA sequence alignment, and the Unix diff command.

State: dp[i][j] = minimum operations to convert word1[0..i-1] to word2[0..j-1].
Recurrence:

• If word1[i-1] === word2[j-1]: no operation needed. dp[i][j] = dp[i-1][j-1].
• Else, take the minimum of three operations:
  • Replace word1[i-1] with word2[j-1]: cost 1 + dp[i-1][j-1]
  • Delete word1[i-1]: cost 1 + dp[i-1][j]
  • Insert word2[j-1] after position i: cost 1 + dp[i][j-1]

Base cases: dp[i][0] = i (delete i characters to get empty string). dp[0][j] = j (insert j characters from empty string).

function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
  );
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1],  // replace
          dp[i - 1][j],      // delete
          dp[i][j - 1]       // insert
        );
      }
    }
  }
  
  return dp[m][n];
}

Table for "horse" → "ros":

       ""  r  o  s
  ""  [ 0, 1, 2, 3]
  h   [ 1, 1, 2, 3]
  o   [ 2, 2, 1, 2]
  r   [ 3, 2, 2, 2]
  s   [ 4, 3, 3, 2]
  e   [ 5, 4, 4, 3]

Result: dp[5][3] = 3. Three operations: replace 'h'→'r', delete 'r', delete 'e'. ✓

8. 0/1 Knapsack

Given weights [1, 3, 4, 5] and values [1, 4, 5, 7] for items, and capacity W = 7, find maximum value you can carry. Each item used at most once.

The "0/1" name: Each item is either taken (1) or not (0). No fractions, no reuse.

State: dp[i][w] = max value using first i items with capacity w.
Recurrence:

• Skip item i: dp[i][w] = dp[i-1][w]
• Take item i (only if weights[i-1] <= w): dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]
• Take max of both.
  Base cases: dp[0][w] = 0 for all w (no items = 0 value).

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];  // skip item i
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]  // take item i
        );
      }
    }
  }
  
  return dp[n][W];
}

Key difference from Coin Change (unbounded): In knapsack, each item used at most once → use dp[i-1][...] (previous row, same item not available). In coin change, unlimited reuse → use dp[i][...] (current row, same coin still available). This one-line difference separates the two problem types.

Space optimization: Since row i only depends on row i-1, use a 1D array iterated backwards:

function knapsack1D(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  
  for (let i = 0; i < weights.length; i++) {
    // Iterate backwards to prevent using item i twice
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  
  return dp[W];
}

Why backwards? When computing dp[w], we need dp[w - weight[i]] from before item i was considered. If we go forward, dp[w - weight[i]] might already reflect item i being used — allowing it to be reused. Backwards iteration ensures we always read the pre-item-i value.

9. Longest Increasing Subsequence (LIS)

Find the length of the longest strictly increasing subsequence of [10, 9, 2, 5, 3, 7, 101, 18].

Expected: 4 ("2, 3, 7, 101" or "2, 5, 7, 101").

O(n²) DP Solution

State: dp[i] = length of LIS ending at index i (must include nums[i]).
Recurrence: For all j < i where nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1).
Base cases: dp[i] = 1 (every element is an LIS of length 1 by itself).

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  
  return Math.max(...dp);
}

Dry run on [10, 9, 2, 5, 3, 7, 101, 18]:

dp = [1, 1, 1, 1, 1, 1, 1, 1]

i=1 (9): j=0: nums[0]=10 >= 9, skip. dp[1]=1
i=2 (2): j=0: 10>=2 skip. j=1: 9>=2 skip. dp[2]=1
i=3 (5): j=0: 10>=5 skip. j=1: 9>=5 skip. j=2: 2<5 → dp[3]=max(1,dp[2]+1)=2
i=4 (3): j=2: 2<3 → dp[4]=max(1,2)=2. j=3: 5>=3 skip. dp[4]=2
i=5 (7): j=2: 2<7 → dp[5]=2. j=3: 5<7 → dp[5]=max(2,dp[3]+1)=3.
          j=4: 3<7 → dp[5]=max(3,dp[4]+1)=3. dp[5]=3
i=6 (101): all < 101. best: dp[5]+1=4. dp[6]=4
i=7 (18): j=2: dp[2]+1=2. j=3: dp[3]+1=3. j=4: dp[4]+1=3.
           j=5: dp[5]+1=4. j=6: 101>=18 skip. dp[7]=4

max(dp) = 4 ✓

O(n log n) Patience Sorting

Maintain a tails array where tails[i] is the smallest tail element of all LIS of length i+1. Binary search to update.

function lengthOfLIS(nums) {
  const tails = [];
  
  for (const num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;  // replace or extend
  }
  
  return tails.length;
}

tails is always sorted. Binary search finds the leftmost position where tails[pos] >= num. If pos === tails.length, extend (num is larger than all tails). Otherwise, replace tails[pos] with num (found a smaller tail for that LIS length).

This doesn't store the actual LIS, only its length. To reconstruct the LIS, use the O(n²) approach with parent pointers.

10. The Subproblem DAG — Why DP Is Efficient

DP is efficient for exactly the same reason BFS/DFS is O(V + E): each state is computed exactly once.

For Fibonacci:

• States (V): n+1 values (0 through n)
• Dependencies (E): n edges (fib(i) depends on fib(i-1) and fib(i-2))
• Total work: O(V + E) = O(n)

For LCS(m, n):

• States: (m+1)(n+1) cells
• Dependencies: 3 edges per cell (diagonal, up, left)
• Total work: O(m × n)

For Coin Change (amount, |coins|):

• States: amount+1
• Dependencies: |coins| per state
• Total work: O(amount × |coins|)

This is the correct way to analyze DP complexity: count the states and the work per state.

11. State Compression — When to Reduce Dimensions

Often you can reduce dp[i][j] to dp[j] (1D array) if row i only depends on row i-1.

LCS → 1D:

function longestCommonSubsequence(text1, text2) {
  const n = text2.length;
  let dp = new Array(n + 1).fill(0);
  
  for (const ch1 of text1) {
    const prev = [...dp];  // save previous row
    for (let j = 1; j <= n; j++) {
      if (ch1 === text2[j - 1]) {
        dp[j] = prev[j - 1] + 1;
      } else {
        dp[j] = Math.max(prev[j], dp[j - 1]);
      }
    }
  }
  
  return dp[n];
}

Space: O(n) instead of O(m × n).

Rule of thumb: If dp[i][j] depends only on dp[i-1][...] and dp[i][...] (same row, smaller j), you can compress to 1D. Direction of inner loop matters (forward for insert operations, backward for 0/1 choices).

12. DP Patterns — A Field Guide

13. Mental Model: When to Reach for DP

Reach for DP when:

1. The problem asks for an optimum (max, min) or count of ways.
2. You can define a state that fully characterizes a subproblem.
3. You can write a recurrence that expresses the current state in terms of smaller states.
4. The naive recursive solution has overlapping subproblems (same call made multiple times).

Greedy vs DP: Greedy makes the locally optimal choice at each step, never revisiting. DP tries all choices and picks the best. If greedy provably gives the global optimum (usually proven via exchange argument), prefer it — it's simpler and faster. When you can't prove greedy is optimal, use DP.

Signal phrases: "minimum cost", "maximum profit", "number of ways", "can you reach X", "is it possible to partition" — these almost always suggest DP.

14. Real Systems That Use DP

Git diff / Unix diff: The diff algorithm finds the Longest Common Subsequence of lines between two files. The edit script (what to add/delete) is derived from where the two files diverge from their LCS. git diff is LCS on steroids.

Autocorrect / spell checkers: Edit distance (Levenshtein) measures how similar two words are. When you type "recieve", the spell checker finds words within edit distance 1 or 2. Google's "Did you mean?" uses a weighted edit distance across billions of queries.

Sequence alignment (bioinformatics): BLAST (Basic Local Alignment Search Tool) uses DP to align DNA sequences. Needleman-Wunsch (global alignment) and Smith-Waterman (local alignment) are both DP algorithms. Finding that a new gene sequence is 92% similar to a known gene requires DP.

Viterbi algorithm (NLP): Speech recognition, part-of-speech tagging, and DNA sequence analysis all use the Viterbi algorithm, which is DP on Hidden Markov Models. Every time Siri parses your speech, it runs DP.

Video compression (H.264/H.265): Choosing which frames to use as keyframes and which to encode as differences from previous frames is a DP optimization problem. Netflix's per-title encoding is partially a DP optimization.

TCP congestion control: Some variants of TCP use DP-like algorithms to find optimal transmission rates under varying network conditions.

Compiler optimization: Register allocation (assigning program variables to CPU registers to minimize memory access) is solved using graph coloring, which has DP-based exact solutions.

Vocabulary Map

Connect Forward

This is the final chapter of the core DSA curriculum. At this point you have covered every topic that appears in 95%+ of software engineering interviews at any company.

The complete arc:

Big-O (Ch 1) → how to measure efficiency
Arrays + Hash Maps (Ch 2-3) → the two most-used primitives
Recursion + Sorting (Ch 4) → the thinking mode for all recursive algorithms
Two Pointers + Sliding Window (Ch 5-6) → linear-time array algorithms
Stack + Queue (Ch 7) → monotonic patterns, event ordering
Linked Lists (Ch 8) → pointer manipulation, LRU cache
Binary Search (Ch 9) → O(log n) on any monotonic predicate
Trees + BST (Ch 10) → recursive tree algorithms, inorder = sorted
Backtracking (Ch 11) → enumerate all valid solutions
Graphs + BFS/DFS (Ch 12) → connectivity, shortest path, topological order
Dynamic Programming (Ch 13) → optimal overlapping subproblems

Each chapter builds on the previous. Recursion enables trees enables backtracking. Hash maps power BFS's visited sets and DP's memoization cache. Binary search on answer space generalizes to DP state transitions. Graph topological sort IS bottom-up DP order.

What comes next is systems design — which takes the same first-principles approach: understand physical constraints (disk speed, network latency, RAM vs CPU), then derive the right architecture. The distributed systems layer builds on exactly the data structures you've learned: consistent hashing (arrays + modular arithmetic), Cassandra's SSTrees (sorted arrays), Redis's skip lists (linked lists + binary search), Kafka's log (append-only linked list), Zookeeper's watch mechanism (graph traversal on the znode tree).