> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Dynamic Programming

> Master DP through state definition, transitions, and optimization

<img className="block rounded-lg" src="https://mintcdn.com/devweeekends/8SzFxu49daVetHjN/images/dsa-techniques/06-dynamic-programming.svg?fit=max&auto=format&n=8SzFxu49daVetHjN&q=85&s=e0833787504787a4900ebda48f0e097d" alt="Dynamic Programming Pattern" width="1080" height="1080" data-path="images/dsa-techniques/06-dynamic-programming.svg" />

## What is Dynamic Programming?

**Dynamic Programming** solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant computation. It transforms exponential solutions into polynomial ones.

Think of computing Fibonacci numbers naively. `fib(5)` calls `fib(4)` and `fib(3)`. `fib(4)` calls `fib(3)` and `fib(2)`. Notice that `fib(3)` is computed twice -- and the redundancy explodes exponentially. DP eliminates this by storing each result the first time it is computed and reusing it for free afterward. The Fibonacci tree collapses from O(2^n) calls into O(n) lookups.

Two conditions must hold for DP to apply:

1. **Optimal substructure**: The optimal solution to the problem contains optimal solutions to its subproblems. (The shortest path from A to C through B uses the shortest path from A to B.)
2. **Overlapping subproblems**: The same subproblems are solved repeatedly. (If subproblems are independent and non-overlapping, you have divide and conquer instead.)

DP comes in two flavors. **Top-down (memoization)**: write the natural recursion and cache results. **Bottom-up (tabulation)**: fill a table iteratively from smallest subproblems to largest. Both yield the same asymptotic complexity; bottom-up avoids recursion overhead and is easier to space-optimize.

<Note>
  **Quick Recognition**: If you see **"optimal"** (min/max), **"number of ways"**, or **"can we achieve"** combined with **choices at each step**, think DP!
</Note>

<Tip>
  **LeetCode Pattern Recognition Cheatsheet -- the seven DP families you must memorize:**

  * **"max / min over choices"** -- minimum cost path, maximum profit, longest something. Reach for DP first.
  * **"count number of ways"** -- ways to climb stairs, decode strings, partition. Counting DP is `dp[i] += dp[i - k]` style.
  * **"is X possible / can you achieve"** -- boolean DP, e.g. Partition Equal Subset Sum (LC 416), Word Break (LC 139).
  * **Overlapping subproblems plus optimal substructure** -- the two textbook prerequisites. If subproblems do not overlap, it is divide-and-conquer, not DP.

  **Sub-categories every LeetCode grinder must know:**

  | Family                 | Signature                                             | Canonical LeetCode                                                                |
  | ---------------------- | ----------------------------------------------------- | --------------------------------------------------------------------------------- |
  | **1D linear DP**       | `dp[i]` depends on `dp[i-1]`, `dp[i-2]`, ...          | 70 Climbing Stairs, 198 House Robber, 53 Max Subarray, 91 Decode Ways             |
  | **2D grid DP**         | `dp[i][j]` depends on neighbors in a grid             | 62 Unique Paths, 64 Min Path Sum, 221 Maximal Square                              |
  | **0/1 knapsack**       | each item taken at most once; backwards capacity loop | 416 Partition Equal Subset Sum, 494 Target Sum                                    |
  | **Unbounded knapsack** | each item reusable; forward capacity loop             | 322 Coin Change, 518 Coin Change II, 279 Perfect Squares                          |
  | **LCS / LIS family**   | two strings or one sequence, monotonic relation       | 1143 LCS, 300 LIS, 72 Edit Distance, 5 Longest Palindrome                         |
  | **Interval DP**        | `dp[i][j]` over a contiguous range, often O(n^3)      | 312 Burst Balloons, 1547 Min Cost to Cut Stick, 5 Longest Palindrome              |
  | **Tree DP**            | post-order recursion returning a tuple of states      | 337 House Robber III, 124 Max Path Sum, 968 Cameras                               |
  | **Bitmask DP**         | state encodes a set, n at most around 20              | 691 Stickers, 847 Shortest Path Visiting All Nodes, 1125 Smallest Sufficient Team |

  **Three-second recognition rules:**

  * "Subarray" plus "max / min" -> Kadane (1D DP).
  * "Two strings" plus "longest / minimum operations" -> 2D LCS-style.
  * "Choose items to fit a capacity" -> knapsack (0/1 if each item once, unbounded if reusable).
  * "Number of distinct ways to ..." -> counting DP (often coin-change shape).
  * Small n (at most around 20) plus "visit every X" -> bitmask DP.
  * Tree input plus "rob / cover / paint without conflict on edges" -> tree DP.
</Tip>

## Pattern Recognition Checklist

<CardGroup cols={2}>
  <Card title="Use DP When" icon="check">
    * Problem has **optimal substructure**
    * Same **subproblems solved repeatedly**
    * Need to find **min/max/count**
    * **Choices** at each step affect result
    * Can break into **smaller similar problems**
  </Card>

  <Card title="Don't Use When" icon="xmark">
    * **Greedy** choice works (no need to try all)
    * No **overlapping subproblems**
    * Need **all solutions** (use Backtracking)
    * Simple **iteration** is sufficient
  </Card>
</CardGroup>

## When to Use

<CardGroup cols={2}>
  <Card title="Optimal Substructure" icon="sitemap">
    Optimal solution contains optimal solutions to subproblems
  </Card>

  <Card title="Overlapping Subproblems" icon="clone">
    Same subproblems are solved multiple times
  </Card>

  <Card title="Counting Problems" icon="calculator">
    Number of ways to achieve something
  </Card>

  <Card title="Optimization" icon="bullseye">
    Minimize/maximize under constraints
  </Card>
</CardGroup>

## The IDEAL Framework

<Steps>
  <Step title="Identify">
    Recognize it's a DP problem (optimal/count + choices + constraints)
  </Step>

  <Step title="Define">
    Define what dp\[i] or dp\[i]\[j] represents
  </Step>

  <Step title="Express">
    Write the recurrence relation (transition equation)
  </Step>

  <Step title="Analyze">
    Determine base cases and computation order
  </Step>

  <Step title="Look back">
    Optimize space if possible
  </Step>
</Steps>

## Pattern Variations

### 1. 1D DP (Linear)

The simplest DP pattern. The state is a single index (usually position or amount), and each state depends on a constant number of previous states.

**Climbing Stairs**: At step `i`, you could have arrived from step `i-1` (one step) or `i-2` (two steps). So `dp[i] = dp[i-1] + dp[i-2]` -- this is Fibonacci with different base cases.

**Space optimization insight**: Since `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`, you do not need the full array -- just two variables. This reduces space from O(n) to O(1). Always look for this pattern in 1D DP.

**Time: O(n). Space: O(n) or O(1) optimized.**

<CodeGroup>
  ```python Python theme={null}
  def climb_stairs(n):
      """Number of ways to climb n stairs (1 or 2 steps)"""
      if n <= 2:
          return n
      
      # STATE DEFINITION: dp[i] = number of distinct ways to reach step i
      dp = [0] * (n + 1)
      dp[1] = 1   # Base case: one way to reach step 1 (single step)
      dp[2] = 2   # Base case: two ways to reach step 2 (1+1 or 2)
      
      for i in range(3, n + 1):
          # TRANSITION: arrive from one step below OR two steps below
          dp[i] = dp[i-1] + dp[i-2]
      
      return dp[n]

  # SPACE OPTIMIZED: only keep the two most recent values
  def climb_stairs_optimized(n):
      if n <= 2:
          return n
      
      prev2, prev1 = 1, 2       # dp[i-2] and dp[i-1]
      for i in range(3, n + 1):
          prev2, prev1 = prev1, prev2 + prev1
      
      return prev1
  ```

  ```java Java theme={null}
  public int climbStairs(int n) {
      // Number of ways to climb n stairs (1 or 2 steps)
      if (n <= 2) {
          return n;
      }
      
      // dp[i] = ways to reach step i
      int[] dp = new int[n + 1];
      dp[1] = 1;
      dp[2] = 2;
      
      for (int i = 3; i <= n; i++) {
          dp[i] = dp[i-1] + dp[i-2];  // Come from i-1 or i-2
      }
      
      return dp[n];
  }

  // Space optimized
  public int climbStairsOptimized(int n) {
      if (n <= 2) {
          return n;
      }
      
      int prev2 = 1, prev1 = 2;
      for (int i = 3; i <= n; i++) {
          int curr = prev1 + prev2;
          prev2 = prev1;
          prev1 = curr;
      }
      
      return prev1;
  }
  ```

  ```cpp C++ theme={null}
  int climbStairs(int n) {
      // Number of ways to climb n stairs (1 or 2 steps)
      if (n <= 2) {
          return n;
      }
      
      // dp[i] = ways to reach step i
      vector<int> dp(n + 1);
      dp[1] = 1;
      dp[2] = 2;
      
      for (int i = 3; i <= n; i++) {
          dp[i] = dp[i-1] + dp[i-2];  // Come from i-1 or i-2
      }
      
      return dp[n];
  }

  // Space optimized
  int climbStairsOptimized(int n) {
      if (n <= 2) {
          return n;
      }
      
      int prev2 = 1, prev1 = 2;
      for (int i = 3; i <= n; i++) {
          int curr = prev1 + prev2;
          prev2 = prev1;
          prev1 = curr;
      }
      
      return prev1;
  }
  ```
</CodeGroup>

### 2. 2D DP (Grid/Sequence)

When the state depends on two dimensions (e.g., position in a grid, or two indices into two strings), you need a 2D DP table.

**Unique Paths**: Count how many ways a robot can go from the top-left corner to the bottom-right corner of an `m x n` grid, moving only right or down. Each cell `(i, j)` can only be reached from `(i-1, j)` (above) or `(i, j-1)` (left), so `dp[i][j] = dp[i-1][j] + dp[i][j-1]`. The first row and first column are all 1s because there is only one way to reach them (straight line).

**Walked example**: 3x3 grid. `dp[0][*] = [1,1,1]`, `dp[*][0] = [1,1,1]`. `dp[1][1] = dp[0][1] + dp[1][0] = 1+1 = 2`. `dp[1][2] = dp[0][2] + dp[1][1] = 1+2 = 3`. `dp[2][1] = dp[1][1] + dp[2][0] = 2+1 = 3`. `dp[2][2] = dp[1][2] + dp[2][1] = 3+3 = 6`. Answer: 6 paths.

**Space optimization insight**: Row `i` only depends on row `i-1`. So we can use a 1D array of size `n` and update it in place, left to right. `dp[j] += dp[j-1]` effectively computes `old_dp[j] + dp[j-1]` because `dp[j]` still holds the value from the previous row when we read it.

**Time: O(m \* n). Space: O(m \* n) or O(n) optimized.**

<CodeGroup>
  ```python Python theme={null}
  def unique_paths(m, n):
      """Count paths from top-left to bottom-right (right/down only)"""
      # dp[i][j] = paths to reach cell (i, j)
      dp = [[1] * n for _ in range(m)]
      
      for i in range(1, m):
          for j in range(1, n):
              dp[i][j] = dp[i-1][j] + dp[i][j-1]
      
      return dp[m-1][n-1]

  # Space optimized to O(n)
  def unique_paths_optimized(m, n):
      dp = [1] * n
      
      for i in range(1, m):
          for j in range(1, n):
              dp[j] += dp[j-1]
      
      return dp[n-1]
  ```

  ```java Java theme={null}
  public int uniquePaths(int m, int n) {
      // Count paths from top-left to bottom-right (right/down only)
      // dp[i][j] = paths to reach cell (i, j)
      int[][] dp = new int[m][n];
      
      // Initialize first row and column
      for (int i = 0; i < m; i++) dp[i][0] = 1;
      for (int j = 0; j < n; j++) dp[0][j] = 1;
      
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              dp[i][j] = dp[i-1][j] + dp[i][j-1];
          }
      }
      
      return dp[m-1][n-1];
  }

  // Space optimized to O(n)
  public int uniquePathsOptimized(int m, int n) {
      int[] dp = new int[n];
      Arrays.fill(dp, 1);
      
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              dp[j] += dp[j-1];
          }
      }
      
      return dp[n-1];
  }
  ```

  ```cpp C++ theme={null}
  int uniquePaths(int m, int n) {
      // Count paths from top-left to bottom-right (right/down only)
      // dp[i][j] = paths to reach cell (i, j)
      vector<vector<int>> dp(m, vector<int>(n, 1));
      
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              dp[i][j] = dp[i-1][j] + dp[i][j-1];
          }
      }
      
      return dp[m-1][n-1];
  }

  // Space optimized to O(n)
  int uniquePathsOptimized(int m, int n) {
      vector<int> dp(n, 1);
      
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              dp[j] += dp[j-1];
          }
      }
      
      return dp[n-1];
  }
  ```
</CodeGroup>

### 3. Knapsack Pattern

The 0/1 knapsack is the gateway to a huge family of DP problems. At each item, you make a binary choice: **take it or skip it**. This "take or skip" decision structure appears in Partition Equal Subset Sum, Target Sum, Coin Change (bounded), and many more.

**State**: `dp[i][w]` = maximum value achievable using the first `i` items with capacity `w`.

**Transition**: For each item, either skip it (`dp[i-1][w]`) or take it (`dp[i-1][w - weight_i] + value_i`). Take the max.

**Space optimization**: Since row `i` only depends on row `i-1`, use a 1D array. The trick: iterate `w` **backwards** so that `dp[w - weight_i]` still reflects the previous row (not the current one). Iterating forwards accidentally allows item reuse (turning 0/1 into unbounded knapsack).

**Time: O(n \* W). Space: O(n \* W) or O(W) optimized.**

<CodeGroup>
  ```python Python theme={null}
  def knapsack_01(weights, values, capacity):
      """Maximum value within capacity (each item once)"""
      n = len(weights)
      # dp[i][w] = max value using first i items with capacity w
      dp = [[0] * (capacity + 1) for _ in range(n + 1)]
      
      for i in range(1, n + 1):
          for w in range(capacity + 1):
              # OPTION 1: skip item i -- carry forward from previous row
              dp[i][w] = dp[i-1][w]
              
              # OPTION 2: take item i (if it fits)
              if weights[i-1] <= w:
                  dp[i][w] = max(dp[i][w], 
                                dp[i-1][w - weights[i-1]] + values[i-1])
      
      return dp[n][capacity]

  # SPACE OPTIMIZED to O(W) using a single row
  def knapsack_01_optimized(weights, values, capacity):
      dp = [0] * (capacity + 1)
      
      for i in range(len(weights)):
          # CRITICAL: traverse BACKWARDS to avoid reusing the same item
          for w in range(capacity, weights[i] - 1, -1):
              dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
      
      return dp[capacity]
  ```

  ```java Java theme={null}
  public int knapsack01(int[] weights, int[] values, int capacity) {
      // Maximum value within capacity (each item once)
      int n = weights.length;
      // dp[i][w] = max value using first i items with capacity w
      int[][] dp = new int[n + 1][capacity + 1];
      
      for (int i = 1; i <= n; i++) {
          for (int 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];
  }

  // Space optimized
  public int knapsack01Optimized(int[] weights, int[] values, int capacity) {
      int[] dp = new int[capacity + 1];
      
      for (int i = 0; i < weights.length; i++) {
          // Traverse backwards to avoid using same item twice
          for (int w = capacity; w >= weights[i]; w--) {
              dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
          }
      }
      
      return dp[capacity];
  }
  ```

  ```cpp C++ theme={null}
  int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
      // Maximum value within capacity (each item once)
      int n = weights.size();
      // dp[i][w] = max value using first i items with capacity w
      vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
      
      for (int i = 1; i <= n; i++) {
          for (int 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] = max(dp[i][w], 
                      dp[i-1][w - weights[i-1]] + values[i-1]);
              }
          }
      }
      
      return dp[n][capacity];
  }

  // Space optimized
  int knapsack01Optimized(vector<int>& weights, vector<int>& values, int capacity) {
      vector<int> dp(capacity + 1, 0);
      
      for (int i = 0; i < weights.size(); i++) {
          // Traverse backwards to avoid using same item twice
          for (int w = capacity; w >= weights[i]; w--) {
              dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
          }
      }
      
      return dp[capacity];
  }
  ```
</CodeGroup>

### 4. LCS Pattern (Two Strings)

The Longest Common Subsequence (LCS) is the foundation for a huge family of two-string DP problems: edit distance, shortest common supersequence, and diff algorithms.

**State**: `dp[i][j]` = length of the LCS of `text1[:i]` and `text2[:j]`.

**Transition**: If the current characters match (`text1[i-1] == text2[j-1]`), extend the LCS from `dp[i-1][j-1] + 1`. Otherwise, the LCS is the better of skipping one character from either string: `max(dp[i-1][j], dp[i][j-1])`.

**Walked example**: text1 = "ace", text2 = "abcde". Build a 4x6 table. At (1,1): 'a'=='a', dp=1. At (2,3): 'c'=='c', dp=2. At (3,5): 'e'=='e', dp=3. LCS = "ace", length 3.

**Time: O(m \* n). Space: O(m \* n) or O(min(m, n)) optimized** (since each row depends only on the previous row).

<CodeGroup>
  ```python Python theme={null}
  def longest_common_subsequence(text1, text2):
      """Find LCS length of two strings"""
      m, n = len(text1), len(text2)
      # dp[i][j] = LCS of text1[:i] and text2[:j]
      dp = [[0] * (n + 1) for _ in range(m + 1)]
      
      for i in range(1, m + 1):
          for j in range(1, n + 1):
              if text1[i-1] == text2[j-1]:
                  dp[i][j] = dp[i-1][j-1] + 1
              else:
                  dp[i][j] = max(dp[i-1][j], dp[i][j-1])
      
      return dp[m][n]
  ```

  ```java Java theme={null}
  public int longestCommonSubsequence(String text1, String text2) {
      // Find LCS length of two strings
      int m = text1.length(), n = text2.length();
      // dp[i][j] = LCS of text1[:i] and text2[:j]
      int[][] dp = new int[m + 1][n + 1];
      
      for (int i = 1; i <= m; i++) {
          for (int j = 1; j <= n; j++) {
              if (text1.charAt(i-1) == text2.charAt(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];
  }
  ```

  ```cpp C++ theme={null}
  int longestCommonSubsequence(string text1, string text2) {
      // Find LCS length of two strings
      int m = text1.size(), n = text2.size();
      // dp[i][j] = LCS of text1[:i] and text2[:j]
      vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
      
      for (int i = 1; i <= m; i++) {
          for (int 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] = max(dp[i-1][j], dp[i][j-1]);
              }
          }
      }
      
      return dp[m][n];
  }
  ```
</CodeGroup>

### 5. House Robber (Cannot Take Adjacent)

A classic "cannot take adjacent" DP problem. A robber wants to maximize stolen money, but robbing two adjacent houses triggers an alarm.

**State**: `dp[i]` = maximum money obtainable from houses `0..i`.

**Transition**: At house `i`, you either **rob it** (take `nums[i]` plus the best from non-adjacent houses: `dp[i-2] + nums[i]`) or **skip it** (keep `dp[i-1]`). Take the max.

**Walked example**: nums = \[2, 7, 9, 3, 1]. dp\[0]=2, dp\[1]=max(2,7)=7. dp\[2]=max(7, 2+9)=11. dp\[3]=max(11, 7+3)=11. dp\[4]=max(11, 11+1)=12. Answer: 12 (rob houses 0, 2, 4).

**Space optimization**: Since `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`, two variables suffice -- the same rolling-window trick as Climbing Stairs.

**Time: O(n). Space: O(n) or O(1) optimized.**

**Common variation**: House Robber II (circular) -- run the algorithm twice, once excluding the first house and once excluding the last, then take the max.

<CodeGroup>
  ```python Python theme={null}
  def house_robber(nums):
      """Maximum sum without taking adjacent elements"""
      if not nums:
          return 0
      if len(nums) == 1:
          return nums[0]
      
      # dp[i] = max money robbing houses 0..i
      # Either rob house i (dp[i-2] + nums[i]) or skip it (dp[i-1])
      dp = [0] * len(nums)
      dp[0] = nums[0]
      dp[1] = max(nums[0], nums[1])
      
      for i in range(2, len(nums)):
          dp[i] = max(dp[i-1], dp[i-2] + nums[i])
      
      return dp[-1]

  # Space optimized
  def house_robber_optimized(nums):
      prev2, prev1 = 0, 0
      
      for num in nums:
          prev2, prev1 = prev1, max(prev1, prev2 + num)
      
      return prev1
  ```

  ```java Java theme={null}
  public int houseRobber(int[] nums) {
      // Maximum sum without taking adjacent elements
      if (nums.length == 0) return 0;
      if (nums.length == 1) return nums[0];
      
      // dp[i] = max money robbing houses 0..i
      int[] dp = new int[nums.length];
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0], nums[1]);
      
      for (int i = 2; i < nums.length; i++) {
          dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
      }
      
      return dp[nums.length - 1];
  }

  // Space optimized
  public int houseRobberOptimized(int[] nums) {
      int prev2 = 0, prev1 = 0;
      
      for (int num : nums) {
          int curr = Math.max(prev1, prev2 + num);
          prev2 = prev1;
          prev1 = curr;
      }
      
      return prev1;
  }
  ```

  ```cpp C++ theme={null}
  int houseRobber(vector<int>& nums) {
      // Maximum sum without taking adjacent elements
      if (nums.empty()) return 0;
      if (nums.size() == 1) return nums[0];
      
      // dp[i] = max money robbing houses 0..i
      vector<int> dp(nums.size());
      dp[0] = nums[0];
      dp[1] = max(nums[0], nums[1]);
      
      for (int i = 2; i < nums.size(); i++) {
          dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
      }
      
      return dp.back();
  }

  // Space optimized
  int houseRobberOptimized(vector<int>& nums) {
      int prev2 = 0, prev1 = 0;
      
      for (int num : nums) {
          int curr = max(prev1, prev2 + num);
          prev2 = prev1;
          prev1 = curr;
      }
      
      return prev1;
  }
  ```
</CodeGroup>

### 6. Coin Change

An **unbounded knapsack** variant -- each coin can be used unlimited times. The key difference from 0/1 knapsack: we iterate amounts forward (reuse is intentional).

**State**: `dp[i]` = minimum number of coins needed to make amount `i`. **Transition**: For each amount `i`, try every coin: `dp[i] = min(dp[i], dp[i - coin] + 1)`.

**Edge case**: If `dp[amount]` is still infinity, the amount cannot be formed -- return -1.

**Walked example**: coins = \[1, 3, 4], amount = 6. dp = \[0, 1, 2, 1, 1, 2, 2]. Answer: 2 (coins 3+3).

**Time: O(amount \* len(coins)). Space: O(amount).**

<CodeGroup>
  ```python Python theme={null}
  def coin_change(coins, amount):
      """Minimum coins to make amount"""
      # dp[i] = minimum number of coins to make amount i
      dp = [float('inf')] * (amount + 1)
      dp[0] = 0   # Base case: 0 coins needed to make amount 0
      
      for i in range(1, amount + 1):
          for coin in coins:
              if coin <= i and dp[i - coin] != float('inf'):
                  # Using this coin: 1 (this coin) + coins for the remainder
                  dp[i] = min(dp[i], dp[i - coin] + 1)
      
      return dp[amount] if dp[amount] != float('inf') else -1
  ```

  ```java Java theme={null}
  public int coinChange(int[] coins, int amount) {
      // Minimum coins to make amount
      // dp[i] = min coins to make amount i
      int[] dp = new int[amount + 1];
      Arrays.fill(dp, amount + 1);
      dp[0] = 0;
      
      for (int i = 1; i <= amount; i++) {
          for (int coin : coins) {
              if (coin <= i) {
                  dp[i] = Math.min(dp[i], dp[i - coin] + 1);
              }
          }
      }
      
      return dp[amount] > amount ? -1 : dp[amount];
  }
  ```

  ```cpp C++ theme={null}
  int coinChange(vector<int>& coins, int amount) {
      // Minimum coins to make amount
      // dp[i] = min coins to make amount i
      vector<int> dp(amount + 1, amount + 1);
      dp[0] = 0;
      
      for (int i = 1; i <= amount; i++) {
          for (int coin : coins) {
              if (coin <= i) {
                  dp[i] = min(dp[i], dp[i - coin] + 1);
              }
          }
      }
      
      return dp[amount] > amount ? -1 : dp[amount];
  }
  ```
</CodeGroup>

## Classic Problems

<AccordionGroup>
  <Accordion title="1. Climbing Stairs" icon="stairs">
    **Pattern**: 1D DP (Fibonacci-like)

    **State**: dp\[i] = ways to reach step i
  </Accordion>

  <Accordion title="2. Longest Increasing Subsequence" icon="arrow-up">
    **Pattern**: 1D DP with O(n^2) or binary search O(n log n)

    **State**: dp\[i] = LIS ending at index i
  </Accordion>

  <Accordion title="3. Edit Distance" icon="pen">
    **Pattern**: 2D DP on two strings

    **State**: dp\[i]\[j] = min operations to convert s1\[:i] to s2\[:j]
  </Accordion>

  <Accordion title="4. Partition Equal Subset Sum" icon="scale-balanced">
    **Pattern**: 0/1 Knapsack variant

    **State**: dp\[i]\[sum] = can we make sum using first i elements?
  </Accordion>
</AccordionGroup>

## Common Mistakes

<Warning>
  **Avoid These Pitfalls:**

  1. **Vague state definition**: You must be able to state in one sentence what `dp[i]` (or `dp[i][j]`) represents. If you cannot, your transition will be wrong. Write the definition as a comment before coding.
  2. **Missing or wrong base cases**: `dp[0] = 0` for counting stairs but `dp[0] = 1` for counting paths (one way to stay at the origin). Wrong base cases propagate errors to every subsequent cell.
  3. **Wrong iteration order**: In 0/1 knapsack, iterating capacity forward accidentally allows item reuse. In LCS, you must fill row by row left to right. Always draw the dependency arrows before coding.
  4. **Integer overflow**: Problems asking for counts modulo 10^9+7 hint that raw values overflow. Apply the modulus at every addition, not just at the end.
  5. **Returning dp\[n] when you should return dp\[n-1] (or vice versa)**: Off-by-one on the final answer. Trace a small example to verify.
  6. **Jumping to DP before brute force**: In an interview, start with recursive brute force, explain overlapping subproblems, add memoization, then convert to bottom-up. This progression demonstrates your reasoning.
</Warning>

## Debugging Checklist

When your DP solution fails:

<Steps>
  <Step title="Check State Definition">
    Is dp\[i] clearly defined? Can you explain what it represents?
  </Step>

  <Step title="Check Base Cases">
    Have you initialized all necessary base cases correctly?
  </Step>

  <Step title="Check Recurrence">
    Does your transition cover all cases? Any edge cases missed?
  </Step>

  <Step title="Check Iteration Order">
    Are you computing dp\[i] only after dp\[i-1], dp\[i-2], etc.?
  </Step>

  <Step title="Check Return Value">
    Are you returning the right cell? dp\[n] vs dp\[n-1]?
  </Step>
</Steps>

## DP Pattern Categories

| Category        | Examples                      | State Definition                              |
| --------------- | ----------------------------- | --------------------------------------------- |
| **Linear DP**   | Climbing Stairs, House Robber | dp\[i] = answer for first i elements          |
| **Grid DP**     | Unique Paths, Min Path Sum    | dp\[i]\[j] = answer reaching (i,j)            |
| **String DP**   | LCS, Edit Distance            | dp\[i]\[j] = answer for s1\[:i], s2\[:j]      |
| **Knapsack**    | 0/1 Knapsack, Coin Change     | dp\[i]\[w] = answer using i items, capacity w |
| **Interval DP** | Matrix Chain, Burst Balloons  | dp\[i]\[j] = answer for interval \[i,j]       |
| **Tree DP**     | House Robber III              | dp\[node] = answer for subtree at node        |

## Complexity Quick Reference

| Problem Type    | Time  | Space        | Optimization            |
| --------------- | ----- | ------------ | ----------------------- |
| 1D DP           | O(n)  | O(n) → O(1)  | Keep only last 2 values |
| 2D Grid DP      | O(mn) | O(mn) → O(n) | Keep only previous row  |
| String DP (LCS) | O(mn) | O(mn) → O(n) | Keep only previous row  |
| Knapsack        | O(nW) | O(nW) → O(W) | Single row iteration    |
| Interval DP     | O(n³) | O(n²)        | Usually not optimizable |

## Interview Problems by Company

<Tabs>
  <Tab title="Easy">
    | Problem                  | Company      | DP Type          |
    | ------------------------ | ------------ | ---------------- |
    | Climbing Stairs          | All          | 1D Linear        |
    | Min Cost Climbing Stairs | Amazon       | 1D Linear        |
    | Maximum Subarray         | All          | 1D (Kadane's)    |
    | Best Time to Buy Stock   | Amazon       | 1D State Machine |
    | House Robber             | Google, Meta | 1D Linear        |
  </Tab>

  <Tab title="Medium">
    | Problem                   | Company           | DP Type            |
    | ------------------------- | ----------------- | ------------------ |
    | Unique Paths              | All FAANG         | 2D Grid            |
    | Coin Change               | Amazon, Google    | Unbounded Knapsack |
    | LCS                       | Microsoft, Google | 2D String          |
    | Word Break                | Meta, Amazon      | 1D with Dictionary |
    | Longest Increasing Subseq | Google            | 1D + Binary Search |
  </Tab>

  <Tab title="Hard">
    | Problem              | Company      | DP Type     |
    | -------------------- | ------------ | ----------- |
    | Edit Distance        | Google       | 2D String   |
    | Regular Expression   | Meta, Google | 2D String   |
    | Burst Balloons       | Google       | Interval DP |
    | Longest Valid Parens | Meta         | 1D Stack/DP |
    | Interleaving String  | Amazon       | 2D String   |
  </Tab>
</Tabs>

## Interview Tips

<AccordionGroup>
  <Accordion title="How to Explain Your Approach" icon="comments">
    **Script for interviews:**

    1. "I notice this is asking for \[optimal/count], which suggests DP."
    2. "Let me define the state: dp\[i] represents..."
    3. "The recurrence is: dp\[i] = ... because..."
    4. "Base case is dp\[0] = ... because..."
    5. "Time is O(...) and space is O(...), which I can optimize to..."
  </Accordion>

  <Accordion title="When Interviewer Says..." icon="user-tie">
    | Interviewer Says           | You Should Think        |
    | -------------------------- | ----------------------- |
    | "Find minimum/maximum"     | Optimization DP         |
    | "Count the number of ways" | Counting DP             |
    | "Can you achieve X?"       | Boolean DP (true/false) |
    | "Optimize your recursion"  | Add memoization         |
    | "Reduce space complexity"  | Rolling array technique |
  </Accordion>

  <Accordion title="Top-Down vs Bottom-Up" icon="arrows-up-down">
    **Top-Down (Memoization)**:

    * Easier to write (natural recursion)
    * Only computes needed subproblems
    * Can have stack overflow for large inputs

    **Bottom-Up (Tabulation)**:

    * Usually faster (no recursion overhead)
    * Easier to optimize space
    * Must compute all subproblems

    **Recommendation**: Start with top-down, convert to bottom-up if needed.
  </Accordion>
</AccordionGroup>

## How to Derive a DP Recurrence -- The Five-Step Recipe

This is the single most important DP skill. Most failures are not "I cannot code DP," they are "I cannot derive the recurrence." Use these five steps every time, in this exact order:

<Steps>
  <Step title="1. Define dp[i] (or dp[i][j]) in plain English first">
    Write a one-sentence definition of what `dp[i]` means *before* writing any code. Example: "`dp[i]` = the minimum number of coins to make amount `i`." If you cannot finish that sentence cleanly, you have the wrong state.
  </Step>

  <Step title="2. Write the recurrence by considering the last decision">
    Ask: "what was the last move that led to the answer at `dp[i]`?" Enumerate every possible last move. Example for Coin Change: the last coin was some `c` from the coin set, so `dp[i] = min(dp[i - c] + 1)` over all `c <= i`.
  </Step>

  <Step title="3. Identify the base case(s)">
    What is `dp[0]`? What about other small inputs? Coin Change: `dp[0] = 0` (zero coins for amount 0). House Robber: `dp[0] = nums[0]`, `dp[1] = max(nums[0], nums[1])`. A wrong base case shifts every later value.
  </Step>

  <Step title="4. Decide the iteration order">
    `dp[i]` must be computed only after every state it depends on. For 1D DP this is usually left-to-right. For 2D DP it is row-by-row, left-to-right. For 0/1 knapsack with rolling array, capacity must iterate **backwards**. For interval DP, iterate by interval length, smallest first.
  </Step>

  <Step title="5. Optimize space (last, never first)">
    Once correct, ask: does `dp[i]` depend only on `dp[i-1]`? Then drop to two scalars. Does row `i` depend only on row `i-1`? Then drop to a 1D rolling array. Never optimize space before correctness; it makes debugging miserable.
  </Step>
</Steps>

## DP Templates

Three reusable shapes covering the bulk of LeetCode DP problems.

### Top-Down (Memoization)

```python Python theme={null}
from functools import lru_cache

def solve(...):
    @lru_cache(maxsize=None)
    def f(state):
        if base_case(state):
            return base_value(state)
        best = INITIAL
        for next_state, cost in transitions(state):
            best = combine(best, f(next_state) + cost)
        return best
    return f(initial_state)
```

```java Java theme={null}
Map<Long, Integer> memo = new HashMap<>();
int f(long state) {
    if (isBaseCase(state)) return baseValue(state);
    if (memo.containsKey(state)) return memo.get(state);
    int best = INITIAL;
    for (Transition t : transitions(state)) {
        best = combine(best, f(t.nextState) + t.cost);
    }
    memo.put(state, best);
    return best;
}
```

```cpp C++ theme={null}
unordered_map<long long, int> memo;
int f(long long state) {
    if (isBaseCase(state)) return baseValue(state);
    auto it = memo.find(state);
    if (it != memo.end()) return it->second;
    int best = INITIAL;
    for (auto& t : transitions(state)) {
        best = combine(best, f(t.nextState) + t.cost);
    }
    return memo[state] = best;
}
```

### Bottom-Up Tabulation (1D)

```python Python theme={null}
def solve(n):
    dp = [BASE] * (n + 1)
    dp[0] = ...                    # base case(s)
    for i in range(1, n + 1):
        for choice in choices(i):
            dp[i] = combine(dp[i], dp[i - choice.cost] + choice.value)
    return dp[n]
```

### Bottom-Up Tabulation (2D)

```python Python theme={null}
def solve(m, n):
    dp = [[BASE] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = ...                 # base case(s)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = recurrence(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]
```

### Space-Optimized 1D Rolling

```python Python theme={null}
def solve(n):
    prev2, prev1 = BASE, BASE
    for i in range(2, n + 1):
        curr = recurrence(prev1, prev2)
        prev2, prev1 = prev1, curr
    return prev1
```

### Space-Optimized 2D Rolling (one row)

```python Python theme={null}
def solve(m, n):
    dp = [BASE] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # dp[j] currently holds previous row's value
            dp[j] = recurrence(dp[j], dp[j - 1])   # in-place update
    return dp[n]
```

For 0/1 knapsack with rolling array, **iterate `j` backwards** so you read the previous row's value before overwriting it.

## Worked LeetCode Problems

Eight canonical DP problems with full state definition, recurrence derivation, and code in multiple languages. If you can write all eight from scratch in fifteen minutes each, you are senior-ready on DP.

### LC 70 -- Climbing Stairs (Easy, 1D linear)

**Define:** `dp[i]` = number of distinct ways to reach step `i`.

**Recurrence:** to reach step `i`, the last move was either +1 from `i - 1` or +2 from `i - 2`. So `dp[i] = dp[i-1] + dp[i-2]`.

**Base:** `dp[0] = 1` (one way to "be" at the start), `dp[1] = 1`.

```python Python theme={null}
def climbStairs(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1
```

### LC 198 -- House Robber (Medium, 1D linear)

**Define:** `dp[i]` = max money robbed from the first `i` houses.

**Recurrence:** at house `i`, either rob it (`dp[i-2] + nums[i]`) or skip it (`dp[i-1]`). Take the max.

**Base:** `dp[0] = nums[0]`, `dp[1] = max(nums[0], nums[1])`.

```python Python theme={null}
def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1
```

### LC 322 -- Coin Change (Medium, unbounded knapsack)

**Define:** `dp[a]` = minimum coins to make amount `a`. Use `infinity` for unreachable amounts.

**Recurrence:** the last coin was some `c` from `coins`, so `dp[a] = min(dp[a - c] + 1)` over all `c <= a`.

**Base:** `dp[0] = 0`.

**Iteration order:** amount outer (1..amount), coins inner. Forward direction is fine because each coin is reusable (unbounded knapsack).

```python Python theme={null}
def coinChange(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] != INF:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1
```

```java Java theme={null}
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);   // sentinel = unreachable
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
```

**Top-down version (also acceptable in interviews):**

```python Python theme={null}
from functools import lru_cache
def coinChange(coins, amount):
    @lru_cache(maxsize=None)
    def f(a):
        if a == 0: return 0
        if a < 0: return float('inf')
        return min((f(a - c) + 1 for c in coins), default=float('inf'))
    ans = f(amount)
    return -1 if ans == float('inf') else ans
```

### LC 416 -- Partition Equal Subset Sum (Medium, 0/1 knapsack)

**Define:** `dp[s]` = true if we can pick a subset summing to `s` using elements seen so far.

**Recurrence:** for each new element `x`, `dp[s] = dp[s] OR dp[s - x]` for all `s` from `total // 2` down to `x`.

**Base:** `dp[0] = True` (empty subset).

**Iteration order:** elements outer; sum inner **backwards** -- this is the textbook 0/1 vs unbounded distinction. Forward iteration would let one element contribute twice.

```python Python theme={null}
def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):    # backwards!
            dp[s] = dp[s] or dp[s - x]
    return dp[target]
```

### LC 1143 -- Longest Common Subsequence (Medium, 2D string)

**Define:** `dp[i][j]` = length of LCS of `text1[:i]` and `text2[:j]`.

**Recurrence:** if `text1[i-1] == text2[j-1]`, the last characters match: `dp[i][j] = dp[i-1][j-1] + 1`. Otherwise: `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`.

**Base:** `dp[0][*] = dp[*][0] = 0` (empty string has LCS 0 with anything).

```python Python theme={null}
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]
```

### LC 300 -- Longest Increasing Subsequence (Medium, two approaches)

**Approach 1 -- O(n^2) DP**

**Define:** `dp[i]` = length of the longest increasing subsequence ending at index `i`.

**Recurrence:** `dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i])`, or 1 if no such `j`.

```python Python theme={null}
def lengthOfLIS(nums):
    if not nums: return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
```

**Approach 2 -- O(n log n) Patience Sorting**

Maintain `tails[k]` = the smallest possible last element of an increasing subsequence of length `k + 1`. For each `x`, binary-search for the first `tails[i] >= x` and replace it with `x`. The length of `tails` at the end is the LIS length.

```python Python theme={null}
from bisect import bisect_left
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)
```

**Why patience sorting works:** `tails` is strictly increasing. Replacing `tails[i]` with a smaller value keeps future LIS opportunities open. The actual elements of `tails` are not the LIS itself -- only the *length* is correct. Reconstructing the LIS requires extra parent pointers.

### LC 72 -- Edit Distance (Medium-Hard, 2D string)

**Define:** `dp[i][j]` = minimum operations to convert `word1[:i]` into `word2[:j]`.

**Recurrence:** if last characters match, `dp[i][j] = dp[i-1][j-1]` (free). Otherwise, take the min of three operations:

* Insert: `dp[i][j-1] + 1`
* Delete: `dp[i-1][j] + 1`
* Replace: `dp[i-1][j-1] + 1`

**Base:** `dp[0][j] = j` (insert `j` characters), `dp[i][0] = i` (delete `i` characters).

```python Python theme={null}
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1],   # replace
                                   dp[i-1][j],     # delete
                                   dp[i][j-1])     # insert
    return dp[m][n]
```

### LC 5 -- Longest Palindromic Substring (Medium, interval DP)

**Define:** `dp[i][j]` = True if `s[i..j]` is a palindrome.

**Recurrence:** `dp[i][j] = (s[i] == s[j])` and (`j - i < 2` OR `dp[i+1][j-1]`).

**Iteration order:** by length, smallest first. Lengths 1 and 2 are base cases.

```python Python theme={null}
def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length
    return s[start:start + max_len]
```

**Alternative -- expand around center**, which is also O(n^2) but uses O(1) space and is often easier to write under pressure:

```python Python theme={null}
def longestPalindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]
    best = ""
    for i in range(len(s)):
        for cand in (expand(i, i), expand(i, i + 1)):
            if len(cand) > len(best): best = cand
    return best
```

<Warning>
  **DP traps to remember in interviews:**

  1. **Forgetting to memoize a recursive solution -- exponential blowup.** A pure recursive Fibonacci at n equals 40 takes minutes; with `@lru_cache` it is microseconds. Always add the cache before timing.
  2. **Wrong base case shifts the entire table.** `dp[0]` for "ways to make change" is 1 (one way: use no coins). `dp[0]` for "min coins to make change" is 0. Get it right by tracing a tiny example.
  3. **Iteration order matters -- process states in valid topological order.** In 2D grid DP, you must compute row `i-1` before row `i`. In interval DP, smaller intervals before larger. Drawing the dependency arrows on paper saves time.
  4. **0/1 vs unbounded knapsack -- outer/inner loop order differs.** 0/1 knapsack with rolling array iterates capacity *backwards*; unbounded iterates *forwards*. This is the most common silent bug in DP interviews.
  5. **Space optimization requires careful overwrite order.** When dropping from 2D to 1D, decide whether `dp[j]` should hold the *previous* row or the *current* row when you read it. Mistakes here are hard to debug because results "look reasonable" but are off.
  6. **Counting DP with permutations vs combinations.** LC 518 (Coin Change II) puts coins outer, amount inner -- this counts combinations. Reversing the loop order counts permutations, which is a different problem (LC 377 Combination Sum IV).
  7. **Off-by-one on boundaries.** `dp[n]` vs `dp[n-1]` vs `dp[len(s)]`. Trace a tiny input through your code by hand before submitting.
  8. **Top-down with default argument types.** In Python `@lru_cache` will not memoize lists or dicts (unhashable). Convert to tuples or use frozenset.
  9. **Negative numbers in problems that assume non-negative.** Min Subarray Sum and Maximum Product Subarray both have sign-flipping subtleties. The product DP keeps both `min_so_far` and `max_so_far` because a negative times a negative is the new max.
  10. **Missing the modulo when the problem says "answer modulo 10^9 + 7."** Apply mod after every addition, not just at the return.
</Warning>

<Tip>
  **Three sentences to say in any DP interview:**

  * "Let me first define `dp[i]` in plain English, then derive the recurrence by considering the last decision."
  * "I'll start with top-down memoization for clarity, then convert to bottom-up if you want me to optimize space."
  * "Before coding, let me trace this on the example to verify my recurrence and base case."
</Tip>

## Curated LeetCode List

Twelve problems grouped by sub-pattern. This is the minimum viable list for FAANG-grinding. If you have not seen one, schedule it.

| LC # | Problem                        | Difficulty | Sub-category                    |
| ---- | ------------------------------ | ---------- | ------------------------------- |
| 70   | Climbing Stairs                | Easy       | 1D linear (Fibonacci)           |
| 198  | House Robber                   | Easy       | 1D linear                       |
| 53   | Maximum Subarray               | Easy       | 1D Kadane's                     |
| 91   | Decode Ways                    | Medium     | 1D counting                     |
| 62   | Unique Paths                   | Medium     | 2D grid                         |
| 64   | Minimum Path Sum               | Medium     | 2D grid                         |
| 322  | Coin Change                    | Medium     | Unbounded knapsack              |
| 416  | Partition Equal Subset Sum     | Medium     | 0/1 knapsack                    |
| 1143 | Longest Common Subsequence     | Medium     | 2D string                       |
| 300  | Longest Increasing Subsequence | Medium     | LIS, both O(n^2) and O(n log n) |
| 72   | Edit Distance                  | Hard       | 2D string                       |
| 5    | Longest Palindromic Substring  | Medium     | Interval DP                     |
| 312  | Burst Balloons                 | Hard       | Interval DP                     |
| 337  | House Robber III               | Medium     | Tree DP                         |
| 691  | Stickers to Spell Word         | Hard       | Bitmask DP / BFS                |

## Practice Problems

| Problem                    | Difficulty | Link                                                                       |
| -------------------------- | ---------- | -------------------------------------------------------------------------- |
| Climbing Stairs            | Easy       | [LeetCode 70](https://leetcode.com/problems/climbing-stairs/)              |
| House Robber               | Medium     | [LeetCode 198](https://leetcode.com/problems/house-robber/)                |
| Coin Change                | Medium     | [LeetCode 322](https://leetcode.com/problems/coin-change/)                 |
| Longest Common Subsequence | Medium     | [LeetCode 1143](https://leetcode.com/problems/longest-common-subsequence/) |
| Edit Distance              | Medium     | [LeetCode 72](https://leetcode.com/problems/edit-distance/)                |

## Practice Roadmap

<Steps>
  <Step title="Week 1: 1D DP">
    * Solve: Climbing Stairs, House Robber, Max Subarray
    * Focus: State definition and transitions
  </Step>

  <Step title="Week 2: 2D Grid DP">
    * Solve: Unique Paths, Min Path Sum, Triangle
    * Focus: Grid traversal patterns
  </Step>

  <Step title="Week 3: String DP">
    * Solve: LCS, Edit Distance, Palindrome Substring
    * Focus: Two-string state definition
  </Step>

  <Step title="Week 4: Advanced">
    * Solve: Coin Change, Knapsack, Word Break
    * Focus: Recognizing DP variants
  </Step>
</Steps>

<Tip>
  **Interview Tip**: Start with brute force recursion, add memoization, then convert to bottom-up DP, finally optimize space.
</Tip>

## Interview Questions

Deep-dive questions that test real understanding of Dynamic Programming, not just template memorization. Expect interviewers to push past your initial answer into state design, optimization reasoning, and edge cases.

<AccordionGroup>
  <Accordion title="Q1: You're given a recursive solution that's too slow. How do you determine if DP can help, and walk me through converting it step by step." icon="brain">
    **Difficulty:** Foundational

    **What interviewers are really testing:** Whether the candidate has a systematic framework for recognizing DP applicability and converting recursion to DP, or whether they just pattern-match problem titles to memorized solutions. This is the single most important DP skill -- everything else builds on it.

    **Strong answer:**

    * **Two conditions must hold** for DP to apply: (1) **Optimal substructure** -- the optimal solution to the problem contains optimal solutions to subproblems, and (2) **Overlapping subproblems** -- the recursion solves the same subproblem multiple times. If you have the first but not the second (e.g., merge sort), divide-and-conquer is sufficient. If you have neither, DP will not help.
    * **How I verify overlapping subproblems:** Draw the recursion tree for a small input. If you see the same function call appearing in multiple branches, subproblems overlap. For Fibonacci, `fib(3)` appears twice in the tree for `fib(5)`. For merge sort, every recursive call operates on a unique subarray -- no overlap.
    * **Conversion steps:** (1) Identify the recursive function parameters that change -- these become your DP state. (2) Add a memo table (HashMap or array) keyed on those parameters. Before recursing, check the table; after computing, store the result. (3) Optionally, convert to bottom-up by determining the computation order from base cases to the final answer.
    * **The gotcha most candidates miss:** Not every parameter needs to be part of the state. If a parameter is constant across all calls (like the original array), it is not part of the DP state. Only parameters that *change* define the subproblem space.
    * **Complexity impact:** Memoization converts the time complexity from the number of nodes in the recursion tree (often exponential) to the number of *unique* subproblems times the work per subproblem. For Fibonacci: from O(2^n) to O(n) unique states times O(1) work each = O(n).

    ```python theme={null}
    # Step 1: Naive recursion (exponential)
    def fib(n):
        if n <= 1:
            return n
        return fib(n - 1) + fib(n - 2)  # O(2^n) -- recomputes massively

    # Step 2: Add memoization (top-down DP)
    def fib_memo(n, memo={}):
        if n in memo:
            return memo[n]
        if n <= 1:
            return n
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
        return memo[n]  # O(n) time, O(n) space

    # Step 3: Convert to bottom-up (tabulation)
    def fib_dp(n):
        if n <= 1:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]  # O(n) time, O(n) space

    # Step 4: Optimize space
    def fib_optimized(n):
        if n <= 1:
            return n
        prev2, prev1 = 0, 1
        for i in range(2, n + 1):
            prev2, prev1 = prev1, prev2 + prev1
        return prev1  # O(n) time, O(1) space
    ```

    **Red flag answer:** "If the problem says find minimum or count ways, it's DP." This is a surface-level heuristic that fails for greedy problems (which also minimize) and combinatorics (which also count). The real test is overlapping subproblems, not the problem statement keywords. Another red flag: being unable to explain *why* memoization makes Fibonacci O(n) -- saying "it caches results" without connecting that to the number of unique subproblems.

    **Follow-ups:**

    1. Can you give me an example of a problem with optimal substructure but WITHOUT overlapping subproblems? (Answer: merge sort, binary search. These have optimal substructure but each subproblem is unique, so memoization adds no benefit -- plain divide-and-conquer is the right approach.)
    2. When would you prefer top-down (memoization) over bottom-up (tabulation), and vice versa? Give a concrete scenario for each. (Answer: top-down when only a subset of states is reachable -- e.g., a sparse state space where bottom-up would waste time computing unreachable states. Bottom-up when you need space optimization via rolling arrays, or when the recursion depth would cause a stack overflow for large inputs.)
  </Accordion>

  <Accordion title="Q2: In the 0/1 Knapsack space-optimized solution, why do we iterate capacity backwards? What breaks if we go forwards?" icon="triangle-exclamation">
    **Difficulty:** Intermediate

    **What interviewers are really testing:** Whether the candidate truly understands the dependency structure in DP transitions, not just the code template. The backward iteration is the most commonly memorized-but-not-understood detail in knapsack problems. If you cannot explain it, you cannot adapt to variants.

    **Strong answer:**

    * In the 2D knapsack, `dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])`. Notice both options reference row `i-1` -- the *previous* item's row. When we compress to 1D, a single `dp[w]` array represents the "current" row, and we need `dp[w - weight[i]]` to still hold the value from the previous row.
    * **If we iterate forwards** (small w to large w), then when we compute `dp[w]`, the value `dp[w - weight[i]]` has ALREADY been updated in this iteration for item `i`. That means we are effectively reading `dp[i][w - weight[i]]` instead of `dp[i-1][w - weight[i]]`. This allows us to pick item `i` multiple times -- which is the **Unbounded Knapsack**, not 0/1 Knapsack.
    * **Iterating backwards** ensures that when we read `dp[w - weight[i]]`, it still holds the value from the previous item's computation (row `i-1`). By the time we update `dp[w]`, all cells to its left that it depends on are still from the "old" row.
    * **This is the single key insight** that separates 0/1 Knapsack from Unbounded Knapsack in the space-optimized version. Same code, different iteration direction, completely different problems solved.

    ```python theme={null}
    # 0/1 Knapsack: iterate BACKWARDS (each item used at most once)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    # Unbounded Knapsack: iterate FORWARDS (items can repeat)
    for i in range(len(weights)):
        for w in range(weights[i], capacity + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    ```

    **Red flag answer:** "We go backwards to avoid using an item twice" without explaining the mechanism. *Why* does going forwards allow reuse? If the candidate cannot trace through a small example showing that forward iteration reads an already-updated cell, they memorized the rule without understanding it. Even worse: not knowing that forward iteration solves the Unbounded Knapsack -- this is a critical connection.

    **Follow-ups:**

    1. If I now ask you to solve the Unbounded Knapsack (each item can be used unlimited times), what single change do you make? (Answer: iterate capacity forwards instead of backwards. This deliberately allows reading the current row's values, which models reusing items.)
    2. What about the Bounded Knapsack where each item can be used at most K times? Can you still use a 1D array? (Answer: yes, but it is trickier. You can use binary representation -- decompose K copies into groups of 1, 2, 4, ... copies treated as separate items. This reduces to O(n \* log(K) \* W) time. Alternatively, use a sliding window maximum on the 1D array, but that is more complex to implement.)
  </Accordion>

  <Accordion title="Q3: Define the DP state for Edit Distance. Why is `dp[i][j]` defined as operations on prefixes, not suffixes or substrings?" icon="pen">
    **Difficulty:** Intermediate

    **What interviewers are really testing:** Whether the candidate understands that the state definition is a *design choice* that affects everything -- the recurrence, base cases, and whether the problem even decomposes cleanly. Strong candidates can articulate why one state definition works and another does not.

    **Strong answer:**

    * `dp[i][j]` = minimum operations to convert `word1[0..i-1]` to `word2[0..j-1]` (first `i` characters of word1 into first `j` characters of word2).
    * **Why prefixes work:** Prefixes have a natural inductive structure. Once you know how to convert `word1[0..i-1]` to `word2[0..j-1]`, extending by one character gives you exactly three choices: insert (`dp[i][j-1] + 1`), delete (`dp[i-1][j] + 1`), or replace/match (`dp[i-1][j-1] + 0 or 1`). Each choice reduces the problem to a *strictly smaller* prefix pair.
    * **Why suffixes would also work** but are less natural: you could define `dp[i][j]` as operations on `word1[i..]` to `word2[j..]`, but the base cases become `dp[m][j] = n - j` and `dp[i][n] = m - i`, and the recurrence builds from the bottom-right corner. It is mathematically equivalent but harder to think about and code correctly.
    * **Why arbitrary substrings do NOT work:** If you define `dp[i][j]` as the edit distance between arbitrary substrings, you have no way to decompose the problem without knowing the endpoints of the substrings. The state would need four parameters `(i1, j1, i2, j2)`, which is O(n^2 \* m^2) -- far worse than O(n \* m).
    * **Base cases from the state definition:** `dp[0][j] = j` (inserting `j` characters to build `word2[0..j-1]` from empty string), `dp[i][0] = i` (deleting `i` characters from `word1[0..i-1]`). These base cases fall out naturally from the prefix definition.

    ```python theme={null}
    def edit_distance(word1, word2):
        m, n = len(word1), len(word2)
        # dp[i][j] = min ops to convert word1[:i] to word2[:j]
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Base cases: converting to/from empty string
        for i in range(m + 1):
            dp[i][0] = i  # delete all characters
        for j in range(n + 1):
            dp[0][j] = j  # insert all characters

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]  # characters match, no op
                else:
                    dp[i][j] = 1 + 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]
    ```

    **Red flag answer:** Defining the state as "the edit distance between two strings" without specifying *which* substrings or prefixes. Another red flag: not being able to explain what the three transitions (insert, delete, replace) correspond to physically, or confusing which index moves for which operation. If a candidate says "delete means `dp[i-1][j-1]`" they have the operations mixed up.

    **Follow-ups:**

    1. How would you reconstruct the actual sequence of operations (not just the minimum count)? (Answer: backtrack through the DP table from `dp[m][n]`. At each cell, check which of the three transitions was chosen by comparing values. This takes O(m + n) additional time and reveals the edit script.)
    2. Can you optimize Edit Distance to O(min(m, n)) space? What do you lose by doing so? (Answer: yes, use a rolling two-row array since each cell only depends on the current and previous row. You lose the ability to reconstruct the edit sequence -- you would need to use Hirschberg's algorithm, which combines divide-and-conquer with space-optimized DP to achieve O(min(m, n)) space AND O(mn) time while still allowing path reconstruction.)
  </Accordion>

  <Accordion title="Q4: Coin Change asks for the minimum number of coins. Coin Change II asks for the number of combinations. How does the DP formulation differ and why?" icon="coins">
    **Difficulty:** Intermediate

    **What interviewers are really testing:** Whether the candidate understands how a subtle change in what you are counting (minimum vs count, combinations vs permutations) changes the state definition, transition, and even the iteration order. This is where many candidates who memorize one version fall apart.

    **Strong answer:**

    * **Coin Change (minimum coins):** `dp[amount]` = minimum coins to make `amount`. Transition: `dp[i] = min(dp[i], dp[i - coin] + 1)` for each coin. We iterate amounts in the outer loop, coins in the inner loop (or vice versa -- order does not matter for min).
    * **Coin Change II (count combinations):** `dp[amount]` = number of ways to make `amount`. Transition: `dp[i] += dp[i - coin]`. Here, **iteration order is critical**. To count *combinations* (not permutations), coins must be the OUTER loop and amounts the INNER loop. This ensures each coin denomination is considered in order, preventing counting `[1, 2]` and `[2, 1]` as different.
    * **Why the loop order matters for counting:**
      * Coins outer, amounts inner: you process all amounts for coin 1, then all amounts for coin 2, etc. This enforces an ordering on coins used -- you never "go back" to an earlier coin. Result: combinations.
      * Amounts outer, coins inner: for each amount, you try all coins. A later coin can be followed by an earlier coin. Result: permutations.
    * **For min/max, loop order does not matter** because `min` and `max` are commutative and idempotent -- regardless of the order you discover the paths, the minimum stays the same.

    ```python theme={null}
    # Coin Change: minimum coins (loop order doesn't matter)
    def coin_change(coins, amount):
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i and dp[i - coin] != float('inf'):
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

    # Coin Change II: count combinations (coins MUST be outer loop)
    def coin_change_2(coins, amount):
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:               # coins outer = combinations
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]
        return dp[amount]

    # If you swap loops: count permutations instead
    def coin_permutations(coins, amount):
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(1, amount + 1):    # amounts outer = permutations
            for coin in coins:
                if coin <= i:
                    dp[i] += dp[i - coin]
        return dp[amount]
    ```

    **Red flag answer:** Not knowing the difference between combinations and permutations in this context, or thinking loop order never matters. If a candidate writes the counting solution with amounts as the outer loop and claims it counts combinations, that is a fundamental misunderstanding. Another red flag: initializing `dp[0] = 0` for the counting version (it should be `dp[0] = 1` -- there is one way to make amount 0, which is using no coins).

    **Follow-ups:**

    1. What if each coin can only be used once (like 0/1 Knapsack)? How does the solution change? (Answer: iterate coins in the outer loop and amounts BACKWARDS in the inner loop -- same backward trick as 0/1 Knapsack. This prevents reusing the same coin.)
    2. The interviewer modifies the problem: "find the number of permutations that sum to target." Now what changes? (Answer: swap the loops so amounts are outer, coins are inner. This is actually LeetCode 377 -- Combination Sum IV, which despite its name counts permutations.)
  </Accordion>

  <Accordion title="Q5: Longest Increasing Subsequence has an O(n^2) DP solution and an O(n log n) solution. Explain both and when you'd choose each." icon="arrow-up">
    **Difficulty:** Senior

    **What interviewers are really testing:** Whether the candidate can go beyond the standard O(n^2) DP and articulate the clever patience-sorting / binary-search optimization. More importantly, whether they understand the trade-offs and can reconstruct the actual subsequence, not just its length.

    **Strong answer:**

    * **O(n^2) DP approach:** `dp[i]` = length of LIS ending at index `i`. For each `i`, scan all `j < i` where `nums[j] < nums[i]` and take `dp[i] = max(dp[j] + 1)`. Final answer is `max(dp)`.
    * **O(n log n) approach (patience sorting):** Maintain an array `tails` where `tails[k]` = smallest tail element of all increasing subsequences of length `k + 1`. For each element, binary search `tails` to find where it fits. If it is larger than all tails, append (extends the longest subsequence). Otherwise, replace the first tail that is >= the element (this keeps tails as small as possible for future extension).
    * **Critical insight most people miss:** The `tails` array is NOT the LIS itself. It is always sorted, which is what enables binary search, but its contents at any point do not form a valid subsequence of the original array. To reconstruct the actual LIS, you need a separate parent-pointer array.
    * **When to choose which:**
      * O(n^2): simpler to code, easier to explain, sufficient for n at most around 5000. Also easier to adapt for variants (e.g., longest non-decreasing subsequence, count of LIS, etc.).
      * O(n log n): necessary when n is large (10^5 or more). But it is harder to modify for variants -- for example, counting the number of LIS of maximum length is significantly more complex with the binary search approach.

    ```python theme={null}
    # O(n^2) DP: simple, easy to extend for variants
    def lis_dp(nums):
        n = len(nums)
        dp = [1] * n  # Every element is a subsequence of length 1
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

    # O(n log n) patience sorting with binary search
    import bisect
    def lis_binary_search(nums):
        tails = []
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)   # extends longest subsequence
            else:
                tails[pos] = num    # keeps tail as small as possible
        return len(tails)
    ```

    **Red flag answer:** Claiming the `tails` array IS the LIS. This is a very common misconception. For input `[3, 1, 4, 1, 5, 9, 2, 6]`, the `tails` array might be `[1, 2, 5, 6]` at the end, but the actual LIS is `[1, 4, 5, 9]` or `[1, 4, 5, 6]`. Another red flag: not knowing the O(n^2) solution exists and jumping straight to the binary search version without being able to explain the simpler DP first -- interviewers prefer candidates who show progression from simple to optimized.

    **Follow-ups:**

    1. How would you reconstruct the actual LIS (not just its length) from the O(n log n) approach? (Answer: maintain a parent array that records, for each element, the index of the previous element in its subsequence. When you place an element in `tails`, record its predecessor. Then backtrack from the last element of the longest chain.)
    2. How would you find the NUMBER of distinct longest increasing subsequences? Can the O(n log n) approach handle this efficiently? (Answer: with the O(n^2) approach, maintain a `count[i]` alongside `dp[i]`. When `dp[j] + 1 == dp[i]`, add `count[j]` to `count[i]`. With O(n log n), this requires augmenting the tails structure with Fenwick trees or segment trees -- significantly more complex, O(n log n) is still achievable but the implementation difficulty jumps.)
  </Accordion>

  <Accordion title="Q6: What is interval DP and how does it differ from linear DP? Walk me through Burst Balloons or Matrix Chain Multiplication." icon="layer-group">
    **Difficulty:** Senior

    **What interviewers are really testing:** Whether the candidate can handle DP problems where the state represents a *range* rather than a prefix or single index. Interval DP is a distinct mental model that many candidates never develop, and it is a common Hard-level interview topic at Google and Meta.

    **Strong answer:**

    * **Linear DP** builds solutions left to right: `dp[i]` depends on `dp[i-1]`, `dp[i-2]`, etc. The subproblems are prefixes or suffixes. **Interval DP** builds solutions from smaller intervals to larger ones: `dp[i][j]` represents the answer for the range `[i, j]`, and you try every possible split point `k` in between.
    * **The key pattern:** `dp[i][j] = optimize over all k in [i, j] of (dp[i][k] + dp[k][j] + cost of combining)`. You iterate by *interval length*, starting from length 1 (or 2), building up to the full range.
    * **Burst Balloons (LC 312) walkthrough:**
      * Reframe: instead of "which balloon to burst first," think "which balloon to burst LAST in range `[i, j]`." If balloon `k` is burst last in `[i, j]`, the coins gained are `nums[i-1] * nums[k] * nums[j+1]` (the boundaries are still intact because `k` is the last to go).
      * `dp[i][j]` = max coins from bursting all balloons in range `[i, j]`.
      * Transition: `dp[i][j] = max over k in [i, j] of (dp[i][k-1] + nums[i-1] * nums[k] * nums[j+1] + dp[k+1][j])`.
      * **The non-obvious insight:** thinking about the LAST element to remove rather than the first. This is because when you burst a balloon, it changes the neighbors of adjacent balloons -- forward simulation is a nightmare. But if you think about which is burst *last*, the two sub-intervals `[i, k-1]` and `[k+1, j]` are independent.
    * **Complexity:** O(n^3) time, O(n^2) space. The triple loop: interval length, start position, and split point.

    ```python theme={null}
    def max_coins(nums):
        # Pad with 1s at boundaries
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in range(n)]

        # Iterate by interval length
        for length in range(1, n - 1):        # length of interval
            for i in range(1, n - length):     # start of interval
                j = i + length - 1             # end of interval
                for k in range(i, j + 1):      # last balloon to burst
                    coins = nums[i - 1] * nums[k] * nums[j + 1]
                    coins += dp[i][k - 1] + dp[k + 1][j]
                    dp[i][j] = max(dp[i][j], coins)

        return dp[1][n - 2]
    ```

    **Red flag answer:** Trying to simulate bursting balloons left to right or trying a greedy approach ("burst the smallest first"). Greedy fails because the order affects neighbor relationships. Another red flag: defining the state as `dp[i]` = "max coins after bursting balloon i" -- this does not capture enough information because the answer depends on which other balloons are still present.

    **Follow-ups:**

    1. In Matrix Chain Multiplication, the split point `k` determines where you "cut" the chain. How is this similar to Burst Balloons, and what is the state? (Answer: `dp[i][j]` = minimum multiplications to compute the product of matrices `i` through `j`. Split at `k`: `dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j])`. Same interval DP structure.)
    2. Can interval DP be done top-down with memoization instead of bottom-up? What are the trade-offs? (Answer: yes, and for Burst Balloons specifically, top-down is often easier to write because you do not need to think about the iteration order by interval length. The trade-off is recursion depth and potential stack overflow for large n, plus slightly higher constant factor from function call overhead.)
  </Accordion>

  <Accordion title="Q7: How do you optimize the space complexity of a 2D DP solution? Walk me through the rolling array technique and when it fails." icon="compress">
    **Difficulty:** Intermediate

    **What interviewers are really testing:** Whether the candidate can analyze dependency structures in DP tables and apply space optimization mechanically. This is a common follow-up after any 2D DP solution and separates candidates who understand the technique from those who just memorize the optimized version.

    **Strong answer:**

    * **The core principle:** Look at which rows (or columns) each cell depends on. If `dp[i][j]` only depends on row `i` and row `i-1`, you only need two rows at any time -- a "current" and a "previous" row. This reduces O(mn) space to O(n).
    * **Rolling array technique:** Use `dp[i % 2][j]` instead of `dp[i][j]`. Row 0 and row 1 alternate as "current" and "previous." After processing row `i`, row `i-2` is no longer needed and can be overwritten.
    * **Single-row optimization (even better):** In some problems like Unique Paths, you can use a single 1D array where `dp[j]` represents the current row being built. When you update `dp[j] += dp[j-1]`, the `dp[j]` on the right side still holds the value from the previous row (which is the "up" neighbor), and `dp[j-1]` has already been updated to the current row (which is the "left" neighbor). This works because the dependency is only on `dp[i-1][j]` and `dp[i][j-1]`.
    * **When it FAILS:**
      1. When the cell depends on more than two rows (e.g., `dp[i][j]` depends on `dp[i-1]`, `dp[i-2]`, etc.). You need to keep more rows.
      2. When you need to **reconstruct the solution path** (not just the optimal value). Space optimization destroys the full table, so you cannot backtrack. You would need Hirschberg's divide-and-conquer trick to get both O(n) space and path reconstruction.
      3. **Interval DP:** `dp[i][j]` depends on arbitrary sub-intervals, not just adjacent rows. Rolling arrays do not help here.

    ```python theme={null}
    # Before: O(mn) space
    def unique_paths(m, n):
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

    # After: O(n) space -- single row
    def unique_paths_optimized(m, n):
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]  # dp[j] (old) = up, dp[j-1] (new) = left
        return dp[n-1]

    # Rolling array for LCS (when you might need two explicit rows)
    def lcs_rolling(text1, text2):
        m, n = len(text1), len(text2)
        prev = [0] * (n + 1)
        curr = [0] * (n + 1)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    curr[j] = prev[j-1] + 1
                else:
                    curr[j] = max(prev[j], curr[j-1])
            prev, curr = curr, [0] * (n + 1)
        return prev[n]
    ```

    **Red flag answer:** "Just use two rows instead of a full table." This is the right idea but not enough -- the interviewer wants to hear you explain WHY two rows suffice (the dependency analysis) and WHEN it does not work. Another red flag: applying the optimization incorrectly by not resetting the current row or by confusing which values are "old" vs "new" in a single-row approach.

    **Follow-ups:**

    1. In the LCS space optimization with a single row, you need a temporary variable to hold `dp[j-1]` from the previous row before it gets overwritten. Walk me through why. (Answer: when computing `dp[j]`, you need `prev[j-1]` -- the diagonal. But `dp[j-1]` has already been overwritten to the current row's value. You need to save it in a `temp` variable before the update. The two-row approach avoids this complexity.)
    2. If your interviewer says "I also need the actual LCS string, not just the length, but still in O(n) space" -- what do you do? (Answer: Hirschberg's algorithm. Divide the first string in half. Use forward DP on the first half and backward DP on the second half to find the optimal split point in the second string. Recurse on each half. Total: O(mn) time, O(n) space, and you get the full path.)
  </Accordion>

  <Accordion title="Q8: Explain how the state machine DP approach works for Best Time to Buy and Sell Stock with Cooldown." icon="chart-line">
    **Difficulty:** Senior

    **What interviewers are really testing:** Whether the candidate can model a DP problem as state transitions (a finite state machine) rather than trying to force it into a simpler 1D/2D mold. State machine DP is the cleanest framework for stock problems and tests sophisticated DP thinking.

    **Strong answer:**

    * **The mental model:** On each day, you are in one of three states: **held** (own a stock), **sold** (just sold today, in cooldown tomorrow), **rest** (not holding and not in cooldown). The DP tracks the maximum profit in each state on each day.
    * **Transitions:**
      * `held[i] = max(held[i-1], rest[i-1] - prices[i])` -- either keep holding, or buy today (can only buy from rest state, not sold/cooldown state).
      * `sold[i] = held[i-1] + prices[i]` -- sell what you are holding.
      * `rest[i] = max(rest[i-1], sold[i-1])` -- either keep resting, or transition from cooldown (sold yesterday, forced to rest today).
    * **Base cases:** `held[0] = -prices[0]`, `sold[0] = 0`, `rest[0] = 0`.
    * **Answer:** `max(sold[n-1], rest[n-1])` -- you should not end holding a stock.
    * **Why state machine is powerful:** The same framework handles all stock variants. No cooldown? Remove the rest state. Transaction limit K? Add a transaction counter to the state. Transaction fee? Subtract fee in the sell transition. The framework is modular.

    ```python theme={null}
    def max_profit_cooldown(prices):
        if not prices:
            return 0

        n = len(prices)
        held = [0] * n
        sold = [0] * n
        rest = [0] * n

        held[0] = -prices[0]
        sold[0] = 0
        rest[0] = 0

        for i in range(1, n):
            held[i] = max(held[i-1], rest[i-1] - prices[i])
            sold[i] = held[i-1] + prices[i]
            rest[i] = max(rest[i-1], sold[i-1])

        return max(sold[n-1], rest[n-1])

    # Space optimized to O(1):
    def max_profit_cooldown_optimized(prices):
        if not prices:
            return 0
        held, sold, rest = -prices[0], 0, 0
        for i in range(1, len(prices)):
            new_held = max(held, rest - prices[i])
            new_sold = held + prices[i]
            new_rest = max(rest, sold)
            held, sold, rest = new_held, new_sold, new_rest
        return max(sold, rest)
    ```

    **Red flag answer:** Trying to solve this with a single `dp[i]` = max profit on day i without tracking whether you are holding a stock. This collapses the state space and makes transitions impossible to define correctly. Another red flag: not realizing that the cooldown constraint means you cannot buy the day after selling, and trying to handle it with ad-hoc conditionals instead of clean state separation.

    **Follow-ups:**

    1. How would you extend this to the "at most K transactions" variant (LC 188)? What changes in the state? (Answer: add a transaction counter: `held[i][k]` and `rest[i][k]`. Buying starts a new transaction, so `held[i][k] = max(held[i-1][k], rest[i-1][k-1] - prices[i])`. This is O(nK) time and can be optimized to O(K) space. When K >= n/2, it degenerates to the unlimited-transactions case.)
    2. Can you draw the state machine diagram for the "with cooldown" variant and prove there are no missing transitions? (Answer: three states, five edges. `rest -> held` (buy), `held -> held` (hold), `held -> sold` (sell), `sold -> rest` (forced cooldown), `rest -> rest` (wait). No edge from `sold -> held` or `sold -> sold` -- that is the cooldown constraint.)
  </Accordion>

  <Accordion title="Q9: What is the difference between top-down and bottom-up DP? When does one fail but the other succeed?" icon="arrows-up-down">
    **Difficulty:** Foundational

    **What interviewers are really testing:** This seems like a softball question, but the real test is whether the candidate knows the *practical* differences that affect production code -- stack overflow risk, cache performance, space optimization feasibility -- not just the textbook "one uses recursion and the other uses loops" answer.

    **Strong answer:**

    * **Top-down (memoization):** Write the natural recursion, add a cache. You solve only the subproblems that are actually needed (lazy evaluation). Pros: (1) easier to write since you think recursively, (2) skips unreachable states automatically. Cons: (1) recursion overhead and stack depth limit -- Python defaults to 1000 frames, and even Java/C++ can overflow for large inputs, (2) harder to optimize space, (3) HashMap-based memo has higher constant factor than array access.
    * **Bottom-up (tabulation):** Fill a table iteratively from base cases to the answer. You must compute ALL subproblems in the right order. Pros: (1) no recursion overhead, (2) enables rolling-array space optimization, (3) better cache locality since you iterate sequentially through memory. Cons: (1) you must figure out the correct iteration order, (2) may compute states that are never needed.
    * **When top-down succeeds but bottom-up is painful:** Sparse state spaces. If your state is `dp[i][j][k]` where only a small fraction of `(i, j, k)` triples are reachable, top-down with a HashMap only visits those states. Bottom-up would allocate and iterate through the full 3D array.
    * **When bottom-up succeeds but top-down fails:** Large input sizes where recursion depth exceeds the stack limit. For example, a DP with n = 10^6 states would crash with a stack overflow in top-down Python. Bottom-up iterates without any stack concern.
    * **In interviews, my strategy:** Start with top-down (easier to get correct), then convert to bottom-up if the interviewer asks for space optimization or if the input size is large.

    ```python theme={null}
    # Top-down: natural but stack-limited
    from functools import lru_cache

    def coin_change_topdown(coins, amount):
        @lru_cache(maxsize=None)
        def dp(remaining):
            if remaining == 0:
                return 0
            if remaining < 0:
                return float('inf')
            return 1 + min(dp(remaining - c) for c in coins)
        result = dp(amount)
        return result if result != float('inf') else -1

    # Bottom-up: iterative, space-optimizable, no stack risk
    def coin_change_bottomup(coins, amount):
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i and dp[i - coin] != float('inf'):
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1
    ```

    **Red flag answer:** "Top-down uses recursion, bottom-up uses loops." This is technically correct but shows zero depth. If the candidate cannot discuss stack overflow, cache performance, space optimization feasibility, or sparse vs dense state spaces, they have not used DP seriously. Another red flag: claiming one is always better than the other without discussing trade-offs.

    **Follow-ups:**

    1. In Python, how would you handle a top-down DP with n = 500,000 states? (Answer: increase the recursion limit with `sys.setrecursionlimit`, but this risks crashing the process. The real answer is to convert to bottom-up. Alternatively, use iterative DFS with an explicit stack to simulate the recursion.)
    2. Can you think of a problem where top-down is asymptotically faster than bottom-up? (Answer: yes -- when the state space is sparse and only a fraction of states are reachable. For example, in a DP over a grid with obstacles where most cells are blocked, top-down only visits reachable cells while bottom-up processes the entire grid.)
  </Accordion>

  <Accordion title="Q10: Walk me through how you'd solve Word Break: given a string and a dictionary, determine if the string can be segmented into dictionary words." icon="spell-check">
    **Difficulty:** Intermediate

    **What interviewers are really testing:** Word Break is a canonical DP problem that tests multiple skills simultaneously: recognizing the DP structure (it looks like it could be backtracking), defining the right state, handling string manipulation efficiently, and discussing the time complexity precisely. It is one of the most frequently asked DP problems at Meta and Amazon.

    **Strong answer:**

    * **State:** `dp[i]` = True if the substring `s[0..i-1]` (first `i` characters) can be segmented into dictionary words. The answer is `dp[n]`.
    * **Transition:** `dp[i]` is True if there exists some `j < i` such that `dp[j]` is True AND `s[j..i-1]` is in the dictionary. In other words, we can segmented up to position `j`, and the remainder from `j` to `i` is a valid word.
    * **Base case:** `dp[0] = True` (the empty string is trivially segmentable).
    * **Optimization:** Convert the dictionary to a HashSet for O(1) lookups. Also, you can limit the inner loop: instead of checking all `j` from 0 to `i-1`, only check positions where `i - j` is at most the length of the longest dictionary word. This prunes significantly.
    * **Complexity:** O(n^2 \* L) where n is the string length and L is the average word length (for substring creation and hash comparison). With the max-word-length optimization, it becomes O(n \* maxLen \* L) in practice.
    * **Why not backtracking?** Pure backtracking without memoization is exponential. Consider the string "aaaaab" with dictionary `["a", "aa", "aaa", ...]` -- every partition of the prefix is valid but the string ultimately cannot be segmented (no word ends with "b"). Backtracking explores exponentially many dead ends. DP avoids this by caching results.

    ```python theme={null}
    def word_break(s, word_dict):
        word_set = set(word_dict)
        max_len = max(len(w) for w in word_set) if word_set else 0
        n = len(s)

        dp = [False] * (n + 1)
        dp[0] = True  # empty string is segmentable

        for i in range(1, n + 1):
            for j in range(max(0, i - max_len), i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break  # no need to check further once True

        return dp[n]
    ```

    **Red flag answer:** Using a brute-force recursive approach without memoization and not recognizing the exponential blowup. Another red flag: defining the state as `dp[i]` = "whether the substring starting at i can be segmented" without being able to code it correctly (confusing 0-indexed vs 1-indexed boundaries is extremely common here). Also watch for candidates who use a Trie for the dictionary but cannot explain what advantage it provides over a HashSet -- a Trie helps when you are checking many prefixes from the same starting position, but for Word Break, a HashSet with the max-length optimization is usually simpler and sufficient.

    **Follow-ups:**

    1. How would you modify this to return ALL possible segmentations (Word Break II, LC 140)? Does the DP approach still work? (Answer: use top-down DP with backtracking to reconstruct all paths. The key is that the number of valid segmentations can be exponential -- e.g., "aaa" with dictionary `["a", "aa", "aaa"]` has 4 segmentations -- so the output itself is exponential. Memoize the list of valid segmentations from each starting position.)
    2. What if the dictionary is extremely large (millions of words) but the input string is short (length 100)? Does your approach change? (Answer: no, because we only look up substrings of the input in the dictionary. The number of lookups is O(n \* maxLen), independent of dictionary size. The HashSet lookup is O(L) where L is the substring length, not affected by dictionary size.)
  </Accordion>
</AccordionGroup>

## Interview Deep-Dive

<AccordionGroup>
  <Accordion title="How do you identify that a problem requires DP rather than greedy or backtracking? Walk through your decision framework on an unfamiliar problem.">
    **Strong Answer:**

    * **Step 1 -- Check for optimal substructure.** Does the optimal solution contain optimal solutions to subproblems? If not, neither greedy nor DP applies.
    * **Step 2 -- Check for overlapping subproblems.** Are the same subproblems solved multiple times? If yes, DP. If subproblems are independent, D\&C. If locally optimal choices suffice, greedy.
    * **Step 3 -- Try to break greedy.** Spend 2-3 minutes constructing a counterexample. For coin change with coins \[1, 3, 4] and target 6: greedy picks 4+1+1=3 coins, but optimal is 3+3=2. Greedy fails, so DP is needed.
    * **Step 4 -- Define the state.** Articulate what `dp[i]` or `dp[i][j]` represents. If you cannot cleanly define the state, you may need a different formulation.
    * **Key signals for DP:** "minimum cost," "maximum profit," "number of ways," "can you achieve X" with choices at each step.
    * **Key signals against DP:** "generate all solutions" (backtracking), "single irrevocable choice per step" (greedy), "no overlapping subproblems" (D\&C).

    **Follow-up: In the Coin Change problem, the loop order does not matter for minimum. But in Coin Change II (counting), coins must be the outer loop. Why?**

    * For min/max, the function is commutative and idempotent -- order does not affect the result. For counting, processing amounts before coins allows \[1,2] and \[2,1] to be counted separately (permutations). Processing coins first enforces an ordering, counting only combinations.
  </Accordion>

  <Accordion title="Explain the rolling array space optimization for 2D DP. When does it work, when does it fail, and what do you lose?">
    **Strong Answer:**

    * **When it works:** When `dp[i][j]` depends only on row `i` and row `i-1`. Keep two rows and alternate. Reduces O(mn) space to O(n).
    * **Single-row optimization:** For Unique Paths, `dp[j] += dp[j-1]` works because `dp[j]` on the right still holds the previous row's value and `dp[j-1]` is already updated to the current row.
    * **When it fails:** (1) Cell depends on more than two rows. (2) Interval DP -- dependencies span arbitrary sub-intervals. (3) Path reconstruction needed -- rolling arrays destroy the full table.
    * **What you lose:** The ability to backtrack through the table. For "just the value" problems, no loss. For "print the actual path," use Hirschberg's algorithm (D\&C + rolling array) for O(n) space with reconstruction.
    * **0/1 Knapsack subtlety:** Iterate the inner loop backwards. Forward iteration reuses updated cells, turning 0/1 into unbounded knapsack.

    **Follow-up: In the LCS single-row optimization, why do you need a temporary variable?**

    * When computing `dp[j]`, you need the diagonal value from the previous row (`old dp[j-1]`). But `dp[j-1]` was already overwritten. Save old `dp[j]` in a temp variable before updating -- it becomes the next iteration's diagonal.
  </Accordion>

  <Accordion title="Compare top-down memoization versus bottom-up tabulation. When does each shine, and when does it fail?">
    **Strong Answer:**

    * **Top-down:** Easier to write (add cache to recursion). Only computes reachable states. Natural for tree DP. Fails on deep recursion (Python limit \~1000). HashMap memo has higher constant factor than array access.
    * **Bottom-up:** No recursion overhead. Better cache locality. Enables rolling-array optimization. Must figure out iteration order. Computes ALL states, even unreachable ones.
    * **Top-down shines:** Sparse state spaces (bitmask DP), tree problems, quick prototyping.
    * **Bottom-up shines:** Dense state spaces (grid/string DP), large inputs, space optimization needed.
    * **Interview strategy:** Start top-down (faster to code correctly), convert to bottom-up if asked for optimization.

    **Follow-up: When is top-down asymptotically faster than bottom-up?**

    * When the state space is sparse. A grid DP with 90% blocked cells: top-down visits only reachable cells (10% of grid), while bottom-up processes everything. The asymptotic difference can be significant.
  </Accordion>

  <Accordion title="The state machine DP approach models stock trading. How does adding cooldown, transaction limits, or fees change the transitions?">
    **Strong Answer:**

    * **Base (unlimited transactions):** States: held, rest. `held[i] = max(held[i-1], rest[i-1] - price)`, `rest[i] = max(rest[i-1], held[i-1] + price)`.
    * **With cooldown:** Add sold state. `sold[i] = held[i-1] + price`, `rest[i] = max(rest[i-1], sold[i-1])`, `held[i] = max(held[i-1], rest[i-1] - price)`. Cooldown prevents held from transitioning from sold -- must go through rest.
    * **With K transactions:** Add counter: `held[i][k]`, `rest[i][k]`. Buying starts transaction k. Time: O(nK). When K >= n/2, constraint is lifted.
    * **With fee:** Subtract fee on sell: `rest[i] = max(rest[i-1], held[i-1] + price - fee)`.
    * **Why state machine works:** Each variant adds or modifies one state/transition. The framework is modular.
    * **Space:** All variants optimize to O(1) or O(K) since each day depends only on the previous day.

    **Follow-up: Draw the state machine for the cooldown variant and verify all transitions are covered.**

    * Three states, five edges: rest->held (buy), held->held (hold), held->sold (sell), sold->rest (forced cooldown), rest->rest (wait). No edge from sold->held or sold->sold -- that is the cooldown.
  </Accordion>
</AccordionGroup>

## LeetCode Interview Q\&A

Five LeetCode-grinder-flavored DP questions you should be able to answer cold. Each one comes with a strong-answer framework, full code (top-down and bottom-up where relevant), senior follow-ups, common wrong answers, and further reading.

<AccordionGroup>
  <Accordion title="Q1: Coin Change (LC 322) -- explain top-down and bottom-up approaches and their trade-offs." icon="coins">
    **Strong Answer Framework**

    1. Define state: `dp[a]` = minimum coins to make amount `a`.
    2. Recurrence: the last coin used was some `c`, so `dp[a] = min(dp[a - c] + 1)` over all `c` at most `a`.
    3. Base case: `dp[0] = 0`. Sentinel: `infinity` (or `amount + 1`) for unreachable.
    4. Iteration order: amount outer (1..amount), coins inner. Forward direction works because each coin is reusable.
    5. Both top-down and bottom-up are O(amount \* coins) time and O(amount) space.

    **Real LeetCode Walkthrough -- LC 322**

    Top-down (memoization):

    ```python Python theme={null}
    from functools import lru_cache
    def coinChange(coins, amount):
        @lru_cache(maxsize=None)
        def f(a):
            if a == 0: return 0
            if a < 0: return float('inf')
            return min((f(a - c) + 1 for c in coins), default=float('inf'))
        ans = f(amount)
        return -1 if ans == float('inf') else ans
    ```

    Bottom-up (tabulation):

    ```python Python theme={null}
    def coinChange(coins, amount):
        INF = float('inf')
        dp = [INF] * (amount + 1)
        dp[0] = 0
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a and dp[a - c] != INF:
                    dp[a] = min(dp[a], dp[a - c] + 1)
        return dp[amount] if dp[amount] != INF else -1
    ```

    Trace `coins = [1, 2, 5], amount = 11`: dp = \[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]. Answer: 3 (5+5+1).

    <Note>
      **Senior follow-up 1: Can you reconstruct the actual coins, not just the count?**

      Maintain `parent[a] = c` alongside `dp[a]`, recording which coin gave the best result. To reconstruct, start at `amount`, repeatedly subtract `parent[a]` and prepend it. Adds O(amount) extra space.
    </Note>

    <Note>
      **Senior follow-up 2: What changes for Coin Change II (number of ways) -- LC 518?**

      The recurrence flips to addition: `dp[a] += dp[a - c]`. Critically, the loop order changes: **coins outer, amount inner**. With amount outer, you would count permutations (every ordering of the same coin set), which is LC 377 -- a different problem. The sub-pattern: "combinations: outer item; permutations: outer position."
    </Note>

    <Note>
      **Senior follow-up 3: What if the coins can be negative?**

      The DP breaks because `dp[a - c]` can require unboundedly large amounts (e.g., to reach `a = 5` you could go through `a = 1000` first if you have a -995 coin). The problem becomes ill-posed without an upper bound. With a bound, it becomes shortest-path on a graph -- solve with BFS or Dijkstra.
    </Note>

    **Common Wrong Answers**

    * Greedy "always pick the largest coin." Fails on `coins = [1, 3, 4], amount = 6` (greedy says 3, optimal is 2).
    * Top-down without memoization. Exponential, times out.
    * Forgetting to return -1 for unreachable amounts (sentinel handling).
    * Confusing LC 322 (minimum count) with LC 518 (number of ways) -- different recurrences.

    **Further Reading**

    * LC 518 -- Coin Change II (counting variant)
    * LC 377 -- Combination Sum IV (permutations variant)
    * LC 983 -- Minimum Cost For Tickets
  </Accordion>

  <Accordion title="Q2: Longest Increasing Subsequence (LC 300) -- give both O(n^2) DP and O(n log n) patience sorting." icon="arrow-up-right-dots">
    **Strong Answer Framework**

    1. Start with the natural O(n^2) DP: `dp[i]` = length of LIS ending at index `i`. Recurrence: `dp[i] = 1 + max(dp[j])` over `j < i` with `nums[j] < nums[i]`.
    2. Show that the answer is `max(dp)`, not `dp[n - 1]` -- the LIS does not have to end at the last element.
    3. For the O(n log n) version, introduce patience sorting: maintain `tails[k]` = smallest possible last element of an increasing subsequence of length `k + 1`. For each `x`, binary-search and replace.
    4. Length of `tails` at the end equals LIS length. Note: `tails` is *not* the LIS itself.

    **Real LeetCode Walkthrough -- LC 300**

    O(n^2) DP:

    ```python Python theme={null}
    def lengthOfLIS(nums):
        if not nums: return 0
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
    ```

    O(n log n) Patience Sorting:

    ```python Python theme={null}
    from bisect import bisect_left
    def lengthOfLIS(nums):
        tails = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)
    ```

    Trace `nums = [10, 9, 2, 5, 3, 7, 101, 18]`:

    * 10 -> tails = \[10]
    * 9 -> tails = \[9]
    * 2 -> tails = \[2]
    * 5 -> tails = \[2, 5]
    * 3 -> tails = \[2, 3]
    * 7 -> tails = \[2, 3, 7]
    * 101 -> tails = \[2, 3, 7, 101]
    * 18 -> tails = \[2, 3, 7, 18]

    Answer: 4. The actual LIS could be `[2, 3, 7, 18]` or `[2, 3, 7, 101]` -- the `tails` array does not literally hold the LIS, only the length.

    <Note>
      **Senior follow-up 1: Use bisect\_left vs bisect\_right -- when does it matter?**

      `bisect_left` for strictly increasing (LIS); `bisect_right` for non-decreasing (longest non-decreasing subsequence). Confusing them silently produces the wrong answer on inputs with equal elements. LC 300 wants strictly increasing, so `bisect_left` is correct.
    </Note>

    <Note>
      **Senior follow-up 2: Can you reconstruct the actual LIS, not just its length?**

      Yes, but you need parent pointers. For each `x`, record the index of the predecessor (the element at `tails[i - 1]` at the time `x` was inserted). Walk backwards from the last inserted element. Adds O(n) space.
    </Note>

    <Note>
      **Senior follow-up 3: How does this generalize to the Longest Increasing Subsequence with at-most-K elements removed?**

      Add a dimension: `dp[i][k]` = LIS ending at `i` using at most `k` removals. Recurrence considers two cases per `j < i`: keep `j` (require `nums[j] < nums[i]`) or remove `j` (just inherit `dp[j-1][k-1]`). O(n^2 \* K) time.
    </Note>

    **Common Wrong Answers**

    * Returning `dp[n - 1]` instead of `max(dp)` -- common off-by-one trap.
    * Using `bisect_right` for strict increase -- wrong for inputs with duplicates.
    * Trying to make the patience sorting array hold the actual LIS -- it does not; it only tracks length.
    * Recursive without memoization -- exponential.

    **Further Reading**

    * LC 354 -- Russian Doll Envelopes (2D LIS, sort then 1D LIS)
    * LC 673 -- Number of Longest Increasing Subsequences
    * LC 1671 -- Min Removals to Make Mountain Array
  </Accordion>

  <Accordion title="Q3: Edit Distance (LC 72) -- derive the recurrence from first principles." icon="pen">
    **Strong Answer Framework**

    1. Define: `dp[i][j]` = minimum operations to convert `word1[:i]` to `word2[:j]`.
    2. Reason about the last operation. Three possibilities (plus a free case):
       * Free: if `word1[i-1] == word2[j-1]`, last characters match, no cost: `dp[i][j] = dp[i-1][j-1]`.
       * Replace: change `word1[i-1]` to `word2[j-1]`: `dp[i-1][j-1] + 1`.
       * Delete: drop `word1[i-1]`: `dp[i-1][j] + 1`.
       * Insert: insert `word2[j-1]` at the end of `word1[:i]`: `dp[i][j-1] + 1`.
    3. Base cases: `dp[0][j] = j` (insert j chars from empty), `dp[i][0] = i` (delete all i chars).
    4. Iteration order: row by row, left to right. Each cell depends on three already-computed cells.
    5. Complexity: O(m \* n) time and space; can drop to O(min(m, n)) space with rolling rows.

    **Real LeetCode Walkthrough -- LC 72**

    ```python Python theme={null}
    def minDistance(word1, word2):
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1): dp[i][0] = i
        for j in range(n + 1): dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j-1],   # replace
                                       dp[i-1][j],     # delete
                                       dp[i][j-1])     # insert
        return dp[m][n]
    ```

    Trace `word1 = "horse", word2 = "ros"`. Final dp\[5]\[3] = 3. Path: horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e). Three ops.

    <Note>
      **Senior follow-up 1: Can you do it in O(min(m, n)) space?**

      Yes -- each row depends only on the previous row, so two rolling rows suffice. Watch out: when computing `dp[i][j]`, you need the *previous row's* `dp[i-1][j-1]`, but if you update in place left-to-right with one row, you have already overwritten that cell. Cache it in a temp variable before overwriting.
    </Note>

    <Note>
      **Senior follow-up 2: What if the cost of insert, delete, and replace differ (say, insert = 1, delete = 2, replace = 3)?**

      The recurrence still has the same shape; just multiply each term by its cost: `dp[i][j] = min(dp[i-1][j-1] + replace_cost, dp[i-1][j] + delete_cost, dp[i][j-1] + insert_cost)`. The structure is unchanged because each operation still moves you one cell in the grid.
    </Note>

    <Note>
      **Senior follow-up 3: How do you reconstruct the actual sequence of edits?**

      Walk backwards from `dp[m][n]`. At each cell, look at which neighbor produced the minimum and record the operation. Stop when both indices reach 0. O(m + n) time, O(1) extra (besides the table).
    </Note>

    **Common Wrong Answers**

    * Forgetting the "free" case when characters match -- doubles the answer.
    * Wrong base case (`dp[0][0] = 1` or similar). Empty-to-empty is 0 ops, not 1.
    * Using only two operations (replace and one of insert/delete) -- gives a wrong but plausible answer.

    **Further Reading**

    * LC 583 -- Delete Operations for Two Strings (only delete allowed)
    * LC 712 -- Minimum ASCII Delete Sum
    * LC 1143 -- Longest Common Subsequence (related but simpler)
  </Accordion>

  <Accordion title="Q4: 0/1 Knapsack -- show why iteration order of capacity matters when using a 1D array." icon="briefcase">
    **Strong Answer Framework**

    1. State the 2D version first: `dp[i][w]` = max value using items `0..i-1` with capacity `w`.
    2. Recurrence: take or skip item `i-1`. `dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])` if it fits.
    3. Observe that row `i` depends only on row `i-1`. So compress to 1D.
    4. **Critical:** when iterating with the 1D array, capacity must go *backwards* from `W` down to `weight[i-1]`. Forward iteration would use the *current* row's `dp[w - weight[i-1]]`, which already includes item `i-1`, accidentally allowing it twice -- turning 0/1 into unbounded knapsack.
    5. Walk through a tiny example to demonstrate the bug and the fix.

    **Real Code -- 0/1 Knapsack**

    ```python Python theme={null}
    def knapsack01(weights, values, W):
        dp = [0] * (W + 1)
        for i in range(len(weights)):
            for w in range(W, weights[i] - 1, -1):    # backwards!
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
        return dp[W]
    ```

    **Walked example showing the bug:** `weights = [2], values = [3], W = 4`.

    With *backwards* iteration: `dp` starts `[0, 0, 0, 0, 0]`. Item 0 (w=2, v=3):

    * w=4: `dp[4] = max(0, dp[2] + 3) = max(0, 0 + 3) = 3`.
    * w=3: `dp[3] = max(0, dp[1] + 3) = max(0, 0 + 3) = 3`.
    * w=2: `dp[2] = max(0, dp[0] + 3) = max(0, 0 + 3) = 3`.
    * Final dp = \[0, 0, 3, 3, 3]. Answer dp\[4] = 3. Correct.

    With *forwards* iteration (the bug): `dp` starts `[0, 0, 0, 0, 0]`. Item 0:

    * w=2: `dp[2] = max(0, dp[0] + 3) = 3`.
    * w=3: `dp[3] = max(0, dp[1] + 3) = 3`.
    * w=4: `dp[4] = max(0, dp[2] + 3) = 6`. Wrong! Item used twice.
    * Final dp\[4] = 6. This is the unbounded answer, not 0/1.

    For unbounded knapsack (LC 322 Coin Change family), forward iteration is *correct* -- it gives you item reuse for free.

    <Note>
      **Senior follow-up 1: Why does the 2D version not have this issue?**

      Because `dp[i][*]` is a separate row from `dp[i-1][*]`. The recurrence reads only from row `i-1`, never from row `i` mid-update. The bug emerges only when you compress rows.
    </Note>

    <Note>
      **Senior follow-up 2: Show how the same template solves Partition Equal Subset Sum (LC 416).**

      Same code, but the values become 1s (we just track "achievable sum" as a boolean) and the target is `total // 2`. The 0/1 backward-iteration discipline is identical:

      ```python theme={null}
      dp = [False] * (target + 1)
      dp[0] = True
      for x in nums:
          for s in range(target, x - 1, -1):    # backwards
              dp[s] = dp[s] or dp[s - x]
      return dp[target]
      ```
    </Note>

    <Note>
      **Senior follow-up 3: How do you reconstruct which items were taken?**

      Use the 2D table and walk backwards from `dp[n][W]`. If `dp[i][w] != dp[i-1][w]`, item `i-1` was taken; subtract its weight and continue. The 1D rolling-array version loses this information -- you trade space for traceability.
    </Note>

    **Common Wrong Answers**

    * Forward iteration on the 1D array -- silently solves the wrong problem.
    * Using a 2D array but reading from the *current* row instead of the previous -- same bug, harder to spot.
    * Running greedy by value-per-weight ratio -- works for fractional knapsack, not 0/1.
    * Forgetting the `weights[i] - 1` lower bound -- attempts to access negative indices.

    **Further Reading**

    * LC 416 -- Partition Equal Subset Sum
    * LC 494 -- Target Sum (0/1 with sign decisions)
    * LC 1049 -- Last Stone Weight II (0/1 in disguise)
  </Accordion>

  <Accordion title="Q5: Longest Palindromic Substring (LC 5) -- contrast interval DP and expand-around-center." icon="text-width">
    **Strong Answer Framework**

    1. Define DP state: `dp[i][j]` = True iff `s[i..j]` is a palindrome.
    2. Recurrence: `dp[i][j] = (s[i] == s[j])` AND (`j - i < 2` OR `dp[i+1][j-1]`).
    3. Iteration order: by length, smallest first. Inside each length, slide `i` from 0 to `n - length`.
    4. Both DP and expand-around-center are O(n^2). DP uses O(n^2) space; expand uses O(1).
    5. For the truly optimal O(n) algorithm, mention Manacher -- usually not required to code in interviews, but knowing the name signals depth.

    **Real LeetCode Walkthrough -- LC 5**

    Interval DP version:

    ```python Python theme={null}
    def longestPalindrome(s):
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        start, max_len = 0, 1
        for i in range(n):
            dp[i][i] = True
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
                    dp[i][j] = True
                    if length > max_len:
                        start, max_len = i, length
        return s[start:start + max_len]
    ```

    Expand-around-center version (often easier to write under pressure):

    ```python Python theme={null}
    def longestPalindrome(s):
        def expand(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1; r += 1
            return s[l + 1:r]
        best = ""
        for i in range(len(s)):
            for cand in (expand(i, i), expand(i, i + 1)):
                if len(cand) > len(best): best = cand
        return best
    ```

    Trace `s = "babad"`: expand-around-center gives "bab" (or "aba" -- both valid). DP version fills the table from length 1 up to 5; same answer.

    <Note>
      **Senior follow-up 1: Can you do it in O(n) time?**

      Yes -- Manacher's algorithm. It exploits palindrome symmetry to skip redundant comparisons. Implementation is tricky (involves a "transformed" string with sentinel characters between every pair of original characters), so most interviewers will accept the O(n^2) solution unless they explicitly ask for the optimum.
    </Note>

    <Note>
      **Senior follow-up 2: How do you count *all* palindromic substrings (LC 647)?**

      Same expand-around-center loop, but instead of tracking the longest, increment a counter every time the expand loop runs at least one iteration. O(n^2) time, O(1) space.
    </Note>

    <Note>
      **Senior follow-up 3: What about the Longest Palindromic Subsequence (LC 516) -- not substring?**

      Different problem: characters need not be contiguous. State: `dp[i][j]` = LPS of `s[i..j]`. Recurrence: if `s[i] == s[j]` then `dp[i+1][j-1] + 2`, else `max(dp[i+1][j], dp[i][j-1])`. This is essentially LCS of `s` and `reverse(s)`.
    </Note>

    **Common Wrong Answers**

    * Iterating the DP table by `i` outer and `j` inner -- you would access `dp[i+1][j-1]` before computing it. Iteration order must be by *length* or by *diagonal*.
    * Returning just the length when the problem asks for the substring.
    * Confusing substring (contiguous) with subsequence (LC 516, non-contiguous).
    * Using brute force O(n^3) -- check every substring with a palindrome test. Times out on `n = 1000`.

    **Further Reading**

    * LC 516 -- Longest Palindromic Subsequence
    * LC 647 -- Palindromic Substrings (count)
    * LC 132 -- Palindrome Partitioning II (DP plus interval)
  </Accordion>
</AccordionGroup>