Dynamic Programming

TL;DR

• DP = optimal substructure + overlapping subproblems.
• Top-down (memoization): recursive + cache results.
• Bottom-up (tabulation): iterative, build from smallest subproblem.
• Framework: define state → recurrence relation → base case → compute.

Step 1: When to Use DP

Dynamic programming was invented by Richard Bellman in the 1950s to optimize sequential decision-making problems. The name "dynamic programming" was deliberately chosen to sound impressive to government funders (Bellman's own admission). The core insight is deceptively simple: if you're solving the same subproblem multiple times, solve it once and cache the result. Without DP, problems like Fibonacci grow exponentially (2^n calls); with it, they become linear. DP is the technique that separates candidates who can solve "hard" LeetCode problems from those who can't — roughly 35% of hard problems require it.

Is it a DP problem? Ask:
1. Can I break it into smaller subproblems? (optimal substructure)
2. Do subproblems repeat? (overlapping — same calculation multiple times)
3. Is it asking for: min/max, count ways, is it possible?

Common DP problem types:
• Min/max cost to reach a target
• Count number of ways to do something
• Longest/shortest subsequence
• Yes/no feasibility (can you reach target?)

Step 2: Fibonacci — The DP Hello World

Fibonacci is the canonical DP example because it perfectly illustrates the problem: naive recursion computes fib(3) hundreds of times when calculating fib(10), leading to exponential blowup. It was the problem that made computer scientists formalize memoization in the 1960s. Every DP technique — top-down memo, bottom-up tabulation, and space optimization — can be demonstrated on Fibonacci before applying them to harder problems. Master these three approaches here and you'll apply the same patterns to coin change, knapsack, and LCS.

// ❌ Naive recursion — O(2^n) (exponential!)
function fibBad(n: number): number {
  if (n <= 1) return n;
  return fibBad(n - 1) + fibBad(n - 2); // Recomputes same values!
}

// ✅ Top-down (memoization) — O(n)
function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

// ✅ Bottom-up (tabulation) — O(n) time, O(n) space
function fibTab(n: number): number {
  if (n <= 1) return n;
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

// ✅ Space-optimized — O(n) time, O(1) space
function fibOptimal(n: number): number {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;

  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Step 3: Classic DP Problems

These four problems (climbing stairs, coin change, LIS, house robber) are the most-interviewed DP problems because each teaches a different fundamental pattern. Climbing stairs teaches "count ways" (additive recurrence). Coin change teaches "minimize with choices" (min over options). LIS teaches "optimal ending at i" (quadratic DP with optimization). House robber teaches "include/exclude decisions" (take or skip). If you deeply understand these four, you can decompose 80% of DP interview questions into variations of these patterns.

Climbing Stairs (Ways to reach top)

// Can climb 1 or 2 steps. How many ways to reach step n?
function climbStairs(n: number): number {
  // dp[i] = number of ways to reach step i
  // dp[i] = dp[i-1] + dp[i-2] (come from 1 step back OR 2 steps back)
  if (n <= 2) return n;

  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

Coin Change (Min coins to make amount)

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

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

  return dp[amount] === Infinity ? -1 : dp[amount];
}
// coins = [1, 5, 10], amount = 13
// dp[13] = min(dp[12]+1, dp[8]+1, dp[3]+1) = 4 (10+1+1+1)

Longest Increasing Subsequence (LIS)

function lengthOfLIS(nums: number[]): number {
  // dp[i] = length of LIS ending at index i
  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}
// [10, 9, 2, 5, 3, 7, 101, 18]
// LIS: [2, 5, 7, 101] or [2, 3, 7, 101] → length 4

// O(n log n) optimization with binary search
function lengthOfLIS_Optimal(nums: number[]): number {
  const tails: number[] = []; // tails[i] = smallest tail for LIS of length i+1

  for (const num of nums) {
    let left = 0, right = tails.length;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }
    tails[left] = num;
  }

  return tails.length;
}

House Robber (Can't rob adjacent houses)

function rob(nums: number[]): number {
  // dp[i] = max money from first i houses
  // Choice at house i: rob it (nums[i] + dp[i-2]) or skip it (dp[i-1])
  if (nums.length === 1) return nums[0];

  let prev2 = 0, prev1 = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const current = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}
// [2, 7, 9, 3, 1] → rob 2 + 9 + 1 = 12

Step 4: 2D Dynamic Programming

2D DP was developed for problems where the state depends on two dimensions — comparing two strings (LCS, edit distance), traversing grids, or making decisions with two constraints (items + capacity in knapsack). The mental model shifts from "a line of states" to "a table where each cell depends on its neighbors". These are among the hardest interview problems, but the approach is always the same: define what dp[i][j] means, figure out how to compute it from already-solved cells, and fill the table in the right order.

Unique Paths (Grid)

function uniquePaths(m: number, n: number): number {
  // dp[i][j] = number of ways to reach cell (i, j)
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // From top + from left
    }
  }

  return dp[m - 1][n - 1];
}

Longest Common Subsequence

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  // dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // Match! Extend
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Skip one char
      }
    }
  }

  return dp[m][n];
}
// "abcde", "ace" → 3 ("ace")

0/1 Knapsack

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

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // 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];
}

Step 5: DP Problem-Solving Framework

This framework exists because DP problems feel impossibly varied until you realize they all follow the same five steps. The framework was distilled from competitive programming communities (Codeforces, TopCoder) where contestants needed a systematic approach that works under time pressure. Memorize this process and you'll never freeze on a DP problem again — even if you can't solve it optimally, you'll make structured progress that interviewers reward.

1. DEFINE STATE
   What does dp[i] (or dp[i][j]) represent?
   "dp[i] = the answer for the first i elements"
   "dp[i][j] = the answer using i items with capacity j"

2. RECURRENCE RELATION
   How does dp[i] relate to smaller subproblems?
   dp[i] = max(dp[i-1], dp[i-2] + nums[i])  (house robber)
   dp[i] = min over all coins: dp[i - coin] + 1  (coin change)

3. BASE CASE
   What's the answer for the smallest input?
   dp[0] = 0, dp[1] = 1  (fibonacci)
   dp[0] = 0  (0 coins for amount 0)

4. ITERATION ORDER
   Bottom-up: from base case toward answer
   Make sure subproblems are solved before you need them

5. OPTIMIZATION (optional)
   Can you reduce space? Often dp[i] only depends on dp[i-1] and dp[i-2]
   → Use two variables instead of full array

Step 6: Common DP Patterns

Categorizing DP problems by pattern type came from the competitive programming community's realization that there are really only 6-7 "shapes" of DP. Once you identify which category a problem belongs to, you know the state definition, iteration order, and common optimizations. Linear DP problems have 1D state. Knapsack problems add a capacity dimension. String DP compares two sequences. Interval DP works on subarrays. Bitmask DP handles subset-selection over small sets. Recognizing the pattern is 70% of solving the problem.

Edit Distance (String DP)

function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    new Array(n + 1).fill(0).map((_, j) => (i === 0 ? j : j === 0 ? i : 0))
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // No operation needed
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // Delete
          dp[i][j - 1],     // Insert
          dp[i - 1][j - 1]  // Replace
        );
      }
    }
  }

  return dp[m][n];
}

Interview Questions

1. How do you identify a DP problem?

   • Asks for min/max/count, has optimal substructure (optimal solution uses optimal sub-solutions), and has overlapping subproblems (same computation repeated). Keywords: "minimum cost", "number of ways", "is it possible", "longest/shortest".

2. Top-down vs bottom-up — which to use?

   • Top-down (memoization): more intuitive, only computes needed states, easier to code. Bottom-up (tabulation): no recursion overhead, easier to optimize space, no stack overflow risk. Start with top-down, optimize to bottom-up if needed.

3. How do you optimize DP space?

   • If dp[i] only depends on dp[i-1] (or dp[i-1] and dp[i-2]), use rolling variables instead of full array. 2D → 1D: if current row only uses previous row, keep only two rows.

4. What's the difference between greedy and DP?

   • Greedy: make locally optimal choice at each step (no looking back). DP: consider all options, use subproblem results to find global optimum. Greedy is simpler but doesn't always work. DP guarantees optimal when subproblems overlap.