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

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
 
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] + 1 < dp[i]) {
        dp[i] = dp[i - coin] + 1; // use this coin + solve the remainder
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
 
// coins=[1,3,4], amount=6
// dp[0]=0
// dp[1]=1 (use 1)
// dp[2]=2 (use 1+1)
// dp[3]=1 (use 3)
// dp[4]=1 (use 4)
// dp[5]=2 (use 4+1)
// dp[6]=2 (use 3+3) ✓

House Robber — max money without robbing adjacent houses:

function rob(nums) {
  // dp[i] = max money robbing from houses 0..i
  // Choice at each house: rob it (add nums[i] + dp[i-2]) OR skip it (dp[i-1])
  if (!nums.length) return 0;
  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, nums[i] + prev2); // skip or rob
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Pattern 2 — 2D DP (Two Sequences)

Longest Common Subsequence (LCS):

function lcs(text1, text2) {
  // dp[i][j] = LCS length for text1[0..i-1] and text2[0..j-1]
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => 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; // chars match: extend LCS
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // skip one
      }
    }
  }
  return dp[m][n];
}
 
// text1="abcde", text2="ace"
// LCS = "ace" = length 3

Edit Distance (minimum operations to transform word1 → word2):

function editDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => i || j)
  );
  // dp[i][0] = i (delete all i chars), dp[0][j] = j (insert j chars)
 
  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]; // chars match: no operation needed
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i-1][j],   // delete from word1
          dp[i][j-1],   // insert into word1
          dp[i-1][j-1]  // replace
        );
      }
    }
  }
  return dp[m][n];
}

Pattern 3 — Knapsack

0/1 Knapsack — items with weights and values, maximize value within weight capacity:

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // dp[i][w] = max value using first i items with capacity w
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
 
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // Don't take item i-1
      dp[i][w] = dp[i-1][w];
      // Take item i-1 (if it fits)
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
      }
    }
  }
  return dp[n][capacity];
}

Dynamic Programming (Fibonacci)

1 / 4

[0]

[1]

[2]

[3]

[4]

Base cases: F(0) = 0, F(1) = 1. We want to find F(4).

Common DP Patterns Reference

Pattern	Example Problems	Recurrence Shape
Linear 1D	Climbing Stairs, Coin Change, House Robber	`dp[i] = f(dp[i-1], dp[i-2])`
2D sequences	LCS, Edit Distance, Shortest Common Supersequence	`dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`
0/1 Knapsack	Partition Equal Subset Sum, Target Sum	`dp[i][w] = max(skip, take)`
Unbounded Knapsack	Coin Change, Rod Cutting	`dp[w] = max over all items`
Interval DP	Burst Balloons, Matrix Chain	`dp[i][j] = f(dp[i][k], dp[k+1][j])`
Grid DP	Unique Paths, Minimum Path Sum	`dp[r][c] = f(dp[r-1][c], dp[r][c-1])`

Real-World Frontend Application

React useMemo: Literally memoization — cache the result of an expensive computation and only recompute when dependencies change. The same principle as top-down DP
"Did you mean?" spelling correction: Levenshtein edit distance (a 2D DP problem) powers spellcheckers and fuzzy search
Code editor diff view: git diff, VS Code's diff editor — Myers diff algorithm is based on LCS (a DP problem)
Webpack tree shaking: Deciding which modules to bundle is a variant of the knapsack problem (maximize included code, minimize bundle size)

Common Mistakes

Mistake	What Goes Wrong	Fix
Wrong base case	All results off by one or completely wrong	Always trace through small examples manually
1-indexed vs 0-indexed confusion	Array out of bounds, wrong results	Be explicit: `dp[i]` represents "first i items" vs "item at index i"
Not identifying DP (trying greedy)	Gets wrong answer on tricky cases	Check: does a greedy choice at step 1 always lead to global optimum? No → DP
2D DP when 1D suffices	Wastes memory	Check if `dp[i]` only depends on `dp[i-1]` → use two variables

Key Problems to Solve

#	Problem	Pattern	Difficulty
1	Climbing Stairs	Linear 1D	Easy
2	House Robber	Linear 1D	Medium
3	Coin Change	Unbounded knapsack	Medium
4	Unique Paths	Grid DP	Medium
5	Longest Common Subsequence	2D sequences	Medium
6	Longest Increasing Subsequence	Linear DP (n²) or patience sort (n log n)	Medium
7	Partition Equal Subset Sum	0/1 knapsack	Medium
8	Edit Distance	2D DP	Hard
9	Burst Balloons	Interval DP	Hard
10	Regular Expression Matching	2D DP	Hard

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

function rob(nums) { // dp[i] = max money robbing from houses 0..i // Choice at each house: rob it (add nums[i] + dp[i-2]) OR skip it (dp[i-1]) if (!nums.length) return 0; 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, nums[i] + prev2); // skip or rob prev2 = prev1; prev1 = curr; } return prev1; }

function knapsack(weights, values, capacity) { const n = weights.length; // dp[i][w] = max value using first i items with capacity w const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0)); for (let i = 1; i <= n; i++) { for (let w = 0; w <= capacity; w++) { // Don't take item i-1 dp[i][w] = dp[i-1][w]; // Take item i-1 (if it fits) if (weights[i-1] <= w) { dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]); } } } return dp[n][capacity]; }

Pattern

Example Problems

Recurrence Shape

Linear 1D

Climbing Stairs, Coin Change, House Robber

dp[i] = f(dp[i-1], dp[i-2])

2D sequences

LCS, Edit Distance, Shortest Common Supersequence

dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

0/1 Knapsack

Partition Equal Subset Sum, Target Sum

dp[i][w] = max(skip, take)

Unbounded Knapsack

Coin Change, Rod Cutting

dp[w] = max over all items

Interval DP

Burst Balloons, Matrix Chain

dp[i][j] = f(dp[i][k], dp[k+1][j])

Grid DP

Unique Paths, Minimum Path Sum

dp[r][c] = f(dp[r-1][c], dp[r][c-1])

Mistake

What Goes Wrong

Fix

Wrong base case

All results off by one or completely wrong

Always trace through small examples manually

1-indexed vs 0-indexed confusion

Array out of bounds, wrong results

Be explicit: dp[i] represents "first i items" vs "item at index i"

Not identifying DP (trying greedy)

Gets wrong answer on tricky cases

Check: does a greedy choice at step 1 always lead to global optimum? No → DP

2D DP when 1D suffices

Wastes memory

Check if dp[i] only depends on dp[i-1] → use two variables

Problem

Pattern

Difficulty

Climbing Stairs

Linear 1D

Easy

House Robber

Linear 1D

Medium

Coin Change

Unbounded knapsack

Medium

Unique Paths

Grid DP

Medium

Longest Common Subsequence

2D sequences

Medium

Longest Increasing Subsequence

Linear DP (n²) or patience sort (n log n)

Medium

Partition Equal Subset Sum

0/1 knapsack

Medium

Edit Distance

2D DP

Hard

Burst Balloons

Interval DP

Hard

Regular Expression Matching

2D DP

Hard

Dynamic Programming