Dynamic Programming: From Memoization to Tabulation With 10 Classic Problems Solved

Dynamic programming is the technique that turns “unsolvable in reasonable time” into “solved in milliseconds.” It works by storing solutions to subproblems so you never compute the same thing twice. The challenge is not the technique — it is recognizing when DP applies and identifying the right subproblem structure. This guide teaches both.

⚡ TL;DR: DP applies when: (1) optimal substructure — optimal solution built from optimal sub-solutions, (2) overlapping subproblems — same subproblems solved repeatedly. Two approaches: top-down (recursion + memo cache) or bottom-up (fill table iteratively). Bottom-up avoids call stack overhead.

Recognizing DP problems

// DP signals in problem statement:
// "minimum/maximum number of..."
// "how many ways to..."
// "is it possible to..."
// "longest/shortest subsequence/path..."
// Any problem where brute force explores exponential possibilities

// Template: ask these questions
// 1. Can I break this into smaller subproblems?
// 2. Do subproblems repeat? (overlapping)
// 3. Does optimal subproblem → optimal full solution? (optimal substructure)
// If yes to all: DP likely applies

Problem 1: Fibonacci (the DP gateway)

// Brute force: O(2^n)
// DP memoization (top-down): O(n)
function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  memo.set(n, result);
  return result;
}

// DP tabulation (bottom-up): O(n) time, O(1) space
function fibDP(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

Problem 2: Coin Change (minimum coins)

// Given coins [1,5,10,25] and amount 41, min coins to make change?
// State: dp[i] = minimum coins to make amount i
// Transition: dp[i] = min(dp[i - coin] + 1) for each coin <= i

function coinChange(coins, amount) {
  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;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
coinChange([1, 5, 10, 25], 41); // 4: [25, 10, 5, 1]
// Time: O(amount × coins), Space: O(amount)

Problem 3: Longest Common Subsequence

// LCS("ABCBDAB", "BDCABA") = 4 ("BCBA")
// State: dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
function lcs(s1, s2) {
  const m = s1.length, n = s2.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 (s1[i-1] === s2[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];
}
// Time: O(m×n), Space: O(m×n)
// Used in: diff tools, DNA sequence alignment

Problem 4: 0/1 Knapsack

// Items with weights and values, bag capacity W, max value?
// Each item: take it (0/1) or leave it
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++) {
      // Don't take item i:
      dp[i][w] = dp[i-1][w];
      // Take item i (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][W];
}
// Time: O(n×W), Space: O(n×W) — can optimize to O(W)

DP framework cheat sheet

• ✅ Step 1: Define the state — what does dp[i] or dp[i][j] represent?
• ✅ Step 2: Base case — what is dp[0] or dp[0][0]?
• ✅ Step 3: Transition — how does dp[i] relate to dp[i-1], dp[i-2]?
• ✅ Step 4: Answer — where in the table is the final answer?
• ✅ Top-down (memo) if recursion is more intuitive; bottom-up if stack overflow is a risk
• ❌ Never skip drawing the table — it reveals the transition formula visually

DP problems appear frequently in the FAANG system design interview context, and mastering them requires the recursion fundamentals first. External reference: LeetCode DP problems.