Dynamic Programming

Think of it like this

You're climbing stairs and can take 1 or 2 steps at a time. How many ways to reach step 5?

The naive way: draw the full recursion tree.

ways(5) = ways(4) + ways(3)
ways(4) = ways(3) + ways(2)        ← ways(3) computed TWICE
ways(3) = ways(2) + ways(1)        ← ways(2) computed THREE times
ways(2) = ways(1) + ways(0) = 2
ways(1) = 1
ways(0) = 1

The tree grows exponentially. But notice, ways(3) is computed twice and always gives the same answer. If you cache it the first time, you never recompute it.

That's the entire idea behind DP: cache the results of overlapping subproblems.

Two Requirements for DP

A problem is solvable by DP only if it has:

Overlapping subproblems: The same subproblem appears multiple times in the recursion tree
Optimal substructure: The optimal solution to the full problem can be built from optimal solutions to its subproblems

Two Approaches: Top-Down vs Bottom-Up

Same problem, two implementation styles:
 
Top-down (Memoization):          Bottom-up (Tabulation):
  Start from the question          Start from base cases
  Recurse toward base cases        Build up to the answer
  Cache on the way back            Fill a table iteratively
  Uses recursion + cache           Uses loops + array

Fibonacci, both ways:

// Approach 1: Top-Down (Memoization)
// Start from fib(n), recurse down, cache results
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n]; // cache hit, O(1)
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}
// Time: O(n)  Space: O(n) for cache + O(n) call stack
 
// Approach 2: Bottom-Up (Tabulation)
// Start from base cases, build up to fib(n)
function fibDP(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];
}
// Time: O(n)  Space: O(n)
 
// Approach 3: Space-Optimized Bottom-Up
// Only need the last two values, O(1) space
function fibOptimal(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    [prev2, prev1] = [prev1, prev1 + prev2];
  }
  return prev1;
}
// Time: O(n)  Space: O(1) ✓

How to Identify a DP Problem

Ask these questions about the problem:

"Count the number of ways..." → DP
"Find the minimum/maximum..." → DP
"Is it possible to..." → DP
Can you make a decision at each step that affects future options? → DP
Does a recursive solution recompute the same subproblems? → DP with memoization

The DP Framework (4 Steps)

Step 1: Define the subproblem
  dp[i] = the answer to the problem considering only the first i elements
 
Step 2: Write the recurrence (how dp[i] relates to smaller subproblems)
  dp[i] = some function of dp[i-1], dp[i-2], etc.
 
Step 3: Identify base cases
  dp[0] = ?, dp[1] = ?
 
Step 4: Determine evaluation order
  Usually left-to-right; sometimes 2D tables need specific order

Interactive 2D DP Matrix Studio

0/1 Knapsack Problem

Items: [W:2, V:3], [W:3, V:4], [W:4, V:5], [W:5, V:6]. Bag Capacity: 5.

Recurrence:dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])

Step 1 / 24•4% Complete

State (i \ j)	Cap 0	Cap 1	Cap 2	Cap 3	Cap 4	Cap 5
Base (0)	0	—	—	—	—	—
Item 1 (w=2, v=3)	—	—	—	—	—	—
Item 2 (w=3, v=4)	—	—	—	—	—	—
Item 3 (w=4, v=5)	—	—	—	—	—	—

Active Cell: dp[0][0]

Base Case: 0 items available. Max value is 0.

Target Cell

Dependency Source

Pattern 1, Linear DP (1D Problems)

Coin Change, fewest coins to make amount:

function coinChange(coins, amount) {
  // dp[i] = minimum coins needed to make amount i
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // base case: 0 coins to make amount 0

ways(5) = ways(4) + ways(3) ways(4) = ways(3) + ways(2) ← ways(3) computed TWICE ways(3) = ways(2) + ways(1) ← ways(2) computed THREE times ways(2) = ways(1) + ways(0) = 2 ways(1) = 1 ways(0) = 1

Same problem, two implementation styles: Top-down (Memoization): Bottom-up (Tabulation): Start from the question Start from base cases Recurse toward base cases Build up to the answer Cache on the way back Fill a table iteratively Uses recursion + cache Uses loops + array

// Approach 1: Top-Down (Memoization) // Start from fib(n), recurse down, cache results function fibMemo(n, memo = {}) { if (n <= 1) return n; if (n in memo) return memo[n]; // cache hit, O(1) memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n]; } // Time: O(n) Space: O(n) for cache + O(n) call stack // Approach 2: Bottom-Up (Tabulation) // Start from base cases, build up to fib(n) function fibDP(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]; } // Time: O(n) Space: O(n) // Approach 3: Space-Optimized Bottom-Up // Only need the last two values, O(1) space function fibOptimal(n) { if (n <= 1) return n; let prev2 = 0, prev1 = 1; for (let i = 2; i <= n; i++) { [prev2, prev1] = [prev1, prev1 + prev2]; } return prev1; } // Time: O(n) Space: O(1) ✓

Step 1: Define the subproblem dp[i] = the answer to the problem considering only the first i elements Step 2: Write the recurrence (how dp[i] relates to smaller subproblems) dp[i] = some function of dp[i-1], dp[i-2], etc. Step 3: Identify base cases dp[0] = ?, dp[1] = ? Step 4: Determine evaluation order Usually left-to-right; sometimes 2D tables need specific order

State (i \ j)

Cap 0

Cap 1

Cap 2

Cap 3

Cap 4

Cap 5

Base (0)

—

Item 1 (w=2, v=3)

—

Item 2 (w=3, v=4)

—

Item 3 (w=4, v=5)

—

Dynamic Programming