Dynamic Programming

Dynamic Programming (DP) is arguably the most feared topic in coding interviews. But it becomes manageable once you recognize the pattern: DP = recursion + memoization, applied to problems with overlapping subproblems.

When to Use DP

Look for these signals:

• Question asks for min/max/count of something
• The problem can be broken into similar subproblems
• The problem asks about all possible ways/paths
• Keywords: "minimum number of", "maximum profit", "how many ways", "longest/shortest"

---

The DP Framework

Step 1: Define the state

• What does dp[i] represent?
• "dp[i] = minimum cost to reach step i"
• "dp[i][j] = length of LCS of first i chars of s1 and first j chars of s2"

Step 2: State transition

• How does dp[i] depend on previous states?
• This is the heart of DP — usually requires thinking about the "last step"

Step 3: Base case

• What's the smallest input where the answer is known?
• Often dp[0] or dp[0][0]

Step 4: Answer

• Usually dp[n] or dp[m][n]

---

Classic Problems: 1D DP

Problem 1: Climbing Stairs

You can climb 1 or 2 stairs at a time. How many distinct ways can you climb n stairs?

Think: The number of ways to reach step n = ways to reach step n-1 (then take 1 step) + ways to reach step n-2 (then take 2 steps).

function climbStairs(n) {
  // State: dp[i] = number of ways to reach step i
  // Transition: dp[i] = dp[i-1] + dp[i-2]
  // Base: dp[1] = 1, dp[2] = 2

  if (n <= 2) return n;

  let prev2 = 1, prev1 = 2;

  for (let i = 3; i <= n; i++) {
    [prev2, prev1] = [prev1, prev1 + prev2];
  }

  return prev1;
}

// Examples:
// n=1: 1 way ([1])
// n=2: 2 ways ([1,1] or [2])
// n=3: 3 ways ([1,1,1], [1,2], [2,1])
// n=4: 5 ways

---

Problem 2: House Robber

Rob houses in a row. Cannot rob adjacent houses. Maximize amount robbed.

State: dp[i] = max money robbing houses 0 to i Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

• Either skip house i (take dp[i-1])
• Or rob house i (add nums[i] to dp[i-2], since we can't touch i-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;
}

// Example: [2, 7, 9, 3, 1]
// dp:      [2, 7, 11, 11, 12]
// Answer: 12 (rob houses 0, 2, 4: 2+9+1=12)

---

Problem 3: Coin Change

Given coins of different denominations, find the minimum number of coins to make amount.

State: dp[i] = minimum coins to make amount i Transition: dp[i] = min(dp[i - coin] + 1) for each coin Base: dp[0] = 0

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];
}

// Example: coins = [1, 5, 11], amount = 15
// dp[0] = 0
// dp[1] = 1 (coin 1)
// dp[5] = 1 (coin 5)
// dp[10] = 2 (5+5)
// dp[11] = 1 (coin 11)
// dp[15] = 3 (11+3×1) ... actually wait
// dp[15] = min(dp[14]+1, dp[10]+1, dp[4]+1)
//        = min(4+1, 2+1, 4+1) = 3 (coin 5+5+5)

---

Problem 4: Longest Increasing Subsequence (LIS)

Find the length of the longest strictly increasing subsequence.

O(n²) DP approach:

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);  // Every 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 log n) with binary search — for hard interviews:

function lengthOfLIS_optimized(nums) {
  const tails = [];  // tails[i] = smallest tail element of all LIS of length i+1

  for (const num of nums) {
    let left = 0, right = tails.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }

    tails[left] = num;  // Replace or extend
  }

  return tails.length;
}

// Example: [10, 9, 2, 5, 3, 7, 101, 18]
// tails: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
// LIS length: 4

---

Classic Problems: 2D DP

Problem 5: Longest Common Subsequence (LCS)

Find the length of the longest subsequence common to both strings.

State: dp[i][j] = length of LCS of s1[0..i-1] and s2[0..j-1]

Transition:

• If s1[i-1] === s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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];
}

// text1 = "abcde", text2 = "ace"
// LCS = "ace", length = 3

---

Problem 6: Edit Distance

Minimum operations (insert, delete, replace) to transform word1 to word2.

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];  // 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 in word1
        );
      }
    }
  }

  return dp[m][n];
}

// word1 = "horse", word2 = "ros"
// horse → rorse (replace h→r)
// rorse → rose (delete r)
// rose → ros (delete e)
// Edit distance = 3

---

Problem 7: 0/1 Knapsack

Given items with weights and values, maximize value in a knapsack of capacity W.

function knapsack(weights, values, capacity) {
  const n = weights.length;
  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++) {
      // 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][capacity];
}

---

DP Decision Tree

Use this to decide your DP approach:

Is the problem asking for min/max/count?
    │
    └── YES: Can it be broken into subproblems?
              │
              └── YES: Do subproblems overlap?
                        │
                        ├── YES: Use DP!
                        │         │
                        │         ├── 1D array? → Check previous 1-2 states
                        │         ├── 2D grid?  → Check row above and left
                        │         └── On a tree? → Post-order DFS + memo
                        │
                        └── NO: Use divide & conquer (merge sort, etc.)

---

Common DP Patterns

Pattern	Example Problems
Linear DP	Climbing Stairs, Fibonacci, House Robber
Interval DP	Burst Balloons, Minimum Cost to Merge Stones
Knapsack	Coin Change, Partition Equal Subset Sum, Target Sum
Subsequence	LCS, LIS, Distinct Subsequences
Path in Grid	Minimum Path Sum, Unique Paths
String DP	Edit Distance, Palindrome Partitioning
Tree DP	House Robber III, Diameter of Binary Tree

---

Practice Problems by Difficulty

Easy:

• LeetCode 70 — Climbing Stairs
• LeetCode 121 — Best Time to Buy and Sell Stock
• LeetCode 198 — House Robber
• LeetCode 338 — Counting Bits

Medium:

• LeetCode 322 — Coin Change
• LeetCode 300 — Longest Increasing Subsequence
• LeetCode 1143 — Longest Common Subsequence
• LeetCode 518 — Coin Change 2
• LeetCode 494 — Target Sum
• LeetCode 416 — Partition Equal Subset Sum
• LeetCode 139 — Word Break
• LeetCode 62 — Unique Paths

Hard:

• LeetCode 72 — Edit Distance
• LeetCode 312 — Burst Balloons
• LeetCode 10 — Regular Expression Matching
• LeetCode 115 — Distinct Subsequences
• LeetCode 188 — Best Time to Buy and Sell Stock IV