Dynamic Programming — The Complete Guide

function solve(n: number): number {
  // 1. Define dp array
  const dp = new Array(n + 1).fill(0);

  // 2. Base cases
  dp[0] = baseValue0;
  dp[1] = baseValue1;

  // 3. Fill table (left to right)
  for (let i = 2; i <= n; i++) {
    dp[i] = recurrence(dp[i - 1], dp[i - 2], ...);
    // e.g., dp[i] = dp[i-1] + dp[i-2]           (Climbing Stairs)
    // e.g., dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])  (House Robber)
    // e.g., dp[i] = Math.min(...coins.map(c => dp[i-c]))   (Coin Change)
  }

  // 4. Answer
  return dp[n];
}
// When to use: Climbing Stairs, House Robber, Coin Change,
// Decode Ways, Min Cost Climbing Stairs

function solve(s: string, t: string): number {
  const m = s.length, n = t.length;
  // dp[i][j] = answer for s[0..i-1] and t[0..j-1]
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  // Base cases (first row and first column)
  for (let i = 0; i <= m; i++) dp[i][0] = baseCaseRow(i);
  for (let j = 0; j <= n; j++) dp[0][j] = baseCaseCol(j);

  // Fill table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + matchValue;
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + deleteCost,
          dp[i][j - 1] + insertCost,
          dp[i - 1][j - 1] + replaceCost
        );
      }
    }
  }

  return dp[m][n];
}
// When to use: Longest Common Subsequence, Edit Distance,
// Unique Paths, Minimum Path Sum, Interleaving String

function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  // dp[i][w] = max value using items 0..i-1 with capacity w
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // Option 1: skip item i
      dp[i][w] = dp[i - 1][w];

      // Option 2: 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][capacity];
}
// 0/1 Knapsack: each item used at most once → dp[i-1][...]
// Unbounded Knapsack: items reusable → dp[i][w - weight] (same row)
// When to use: Partition Equal Subset Sum, Target Sum,
// Coin Change (unbounded), Last Stone Weight II

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1); // each element is a subsequence of length 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);
}
// O(n²) time. Can be optimized to O(n log n) with patience sorting.
// When to use: Longest Increasing Subsequence,
// Russian Doll Envelopes, Number of Longest Increasing Subsequence

function rob(nums: number[]): number {
  if (nums.length === 1) return nums[0];

  let prev2 = 0; // dp[i-2]
  let prev1 = 0; // dp[i-1]

  for (const num of nums) {
    const curr = Math.max(
      prev1,          // skip this house
      prev2 + num     // rob this house
    );
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}
// dp[i] = max(dp[i-1], dp[i-2] + nums[i])
// "Take current + best from 2 back" vs "skip current, keep best from 1 back"
// O(n) time, O(1) space.

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

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] !== Infinity) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}
// dp[a] = min over all coins c of (dp[a - c] + 1)
// "Use coin c, then solve for amount a-c"
// O(amount × coins) time, O(amount) space.

function longestCommonSubsequence(text1: string, text2: string): number {
  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; // match — extend diagonal
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // skip one char
      }
    }
  }

  return dp[m][n];
}
// Match: dp[i-1][j-1] + 1 (both characters contribute)
// No match: max(dp[i-1][j], dp[i][j-1]) (skip one character)
// O(m × n) time, O(m × n) space (can optimize to O(n) with rolling array).

                    cs(5)
                   /     \
               cs(4)      cs(3)
              /    \      /    \
          cs(3)  cs(2)  cs(2)  cs(1)
          /  \   / \    / \
       cs(2) cs(1) cs(1) cs(0) cs(1) cs(0)
       / \
    cs(1) cs(0)

Notice: cs(3) is computed 2 times, cs(2) is computed 3 times, cs(1) is computed 5 times.
Total calls: 15 (exponential growth).

With memoization, each unique call is computed ONCE:
  cs(0)=1, cs(1)=1, cs(2)=2, cs(3)=3, cs(4)=5, cs(5)=8
Total calls: 5 (linear).

Bottom-up table:
  i:     0  1  2  3  4  5
  dp[i]: 1  1  2  3  5  8

Answer: dp[5] = 8

coins = [1, 3, 4], amount = 6

dp[0] = 0  (base case: 0 coins for amount 0)

dp[1]: try coin 1 → dp[1-1]+1 = dp[0]+1 = 1
       try coin 3 → 3 > 1, skip
       try coin 4 → 4 > 1, skip
       dp[1] = 1

dp[2]: try coin 1 → dp[1]+1 = 2
       dp[2] = 2

dp[3]: try coin 1 → dp[2]+1 = 3
       try coin 3 → dp[0]+1 = 1  ← better!
       dp[3] = 1

dp[4]: try coin 1 → dp[3]+1 = 2
       try coin 3 → dp[1]+1 = 2
       try coin 4 → dp[0]+1 = 1  ← better!
       dp[4] = 1

dp[5]: try coin 1 → dp[4]+1 = 2
       try coin 3 → dp[2]+1 = 3
       try coin 4 → dp[1]+1 = 2
       dp[5] = 2

dp[6]: try coin 1 → dp[5]+1 = 3
       try coin 3 → dp[3]+1 = 2  ← better!
       try coin 4 → dp[2]+1 = 3
       dp[6] = 2

Answer: 2 coins (3 + 3)

Note: Greedy would pick 4+1+1 = 3 coins. DP finds the true optimum.

text1 = "abcde", text2 = "ace"

       ""  a  c  e
  ""  [ 0, 0, 0, 0 ]
  a   [ 0, 1, 1, 1 ]    a===a → dp[0][0]+1 = 1
  b   [ 0, 1, 1, 1 ]    b≠a,c,e → max of left/above
  c   [ 0, 1, 2, 2 ]    c===c → dp[1][1]+1 = 2
  d   [ 0, 1, 2, 2 ]    d≠a,c,e → max of left/above
  e   [ 0, 1, 2, 3 ]    e===e → dp[3][2]+1 = 3

Answer: dp[5][3] = 3 (LCS = "ace")

Reading the table:
- Diagonal move (match): both characters are in the LCS
- Right or down move (no match): skip one character
- The path from dp[5][3] back to dp[0][0] traces the LCS

Does the problem ask for count/min/max with sequential choices?
├── NO  → Probably not DP. Consider Greedy, BFS, or Backtracking.
└── YES → Does greedy work? (Can you find a counterexample?)
          ├── YES → Use Greedy (simpler, faster).
          └── NO  → Write the brute-force recursion. Do subproblems overlap?
                    ├── NO  → Plain recursion or Divide & Conquer.
                    └── YES → DP! What's the state?
                              ├── One variable (index or amount)?
                              │   → 1D DP (Template 1)
                              │     Climbing Stairs, House Robber, Coin Change
                              ├── Two strings or a grid?
                              │   → 2D DP (Template 2)
                              │     LCS, Edit Distance, Unique Paths
                              ├── Include/exclude items with capacity?
                              │   → Knapsack (Template 3)
                              │     Partition Subset Sum, Target Sum
                              └── Longest subsequence with property?
                                  → LIS (Template 4)
                                    Longest Increasing Subsequence