Dynamic Programming Basics

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into simpler subproblems and storing results to avoid redundant calculations.

---

Why This Matters in Interviews

Dynamic programming is crucial because:

• Optimization problems: Many interview problems are DP problems
• Efficiency: Transforms exponential solutions to polynomial
• Problem patterns: Common patterns appear frequently
• Algorithm design: Tests ability to identify and solve DP problems

Interviewers use DP to assess your problem-solving approach, your ability to optimize solutions, and your understanding of time/space trade-offs.

---

Core Concepts

• Overlapping subproblems: Same subproblems solved multiple times
• Optimal substructure: Optimal solution contains optimal subproblem solutions
• Memoization: Top-down approach, cache results
• Tabulation: Bottom-up approach, build table iteratively
• State definition: What information to store
• Transition: How to compute current state from previous states
• Base cases: Initial values for DP table

---

Detailed Explanation

DP Characteristics

1. Overlapping Subproblems:

Problem can be broken into subproblems that are reused
Example: Fibonacci - fib(n) = fib(n-1) + fib(n-2)

2. Optimal Substructure:

Optimal solution to problem contains optimal solutions to subproblems
Example: Shortest path - shortest path contains shortest subpaths

Memoization (Top-Down)

function fibonacciMemo(n: number, memo: Map<number, number> = new Map()): number {
  // Base case
  if (n <= 1) return n;
  
  // Check memo
  if (memo.has(n)) {
    return memo.get(n)!;
  }
  
  // Compute and memoize
  const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

// Time: O(n)
// Space: O(n)

Tabulation (Bottom-Up)

function fibonacciTab(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];
}

// Time: O(n)
// Space: O(n) - can optimize to O(1)

Space Optimization

function fibonacciOptimized(n: number): number {
  if (n <= 1) return n;
  
  let prev = 0;
  let curr = 1;
  
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

// Time: O(n)
// Space: O(1)

---

Examples

Climbing Stairs

function climbStairs(n: number): number {
  if (n <= 2) return n;
  
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

// Optimized
function climbStairsOptimized(n: number): number {
  if (n <= 2) return n;
  
  let prev = 1;
  let curr = 2;
  
  for (let i = 3; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

Coin Change

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Time: O(amount * coins.length)
// Space: O(amount)

Longest Increasing Subsequence

function lengthOfLIS(nums: number[]): number {
  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);
}

// Time: O(n²)
// Space: O(n)

// Optimized with binary search: O(n log n)
function lengthOfLISOptimized(nums: number[]): number {
  const tails: number[] = [];
  
  for (const num of nums) {
    let left = 0;
    let right = tails.length;
    
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < num) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    if (left === tails.length) {
      tails.push(num);
    } else {
      tails[left] = num;
    }
  }
  
  return tails.length;
}

Edit Distance

function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
  
  // Base cases
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i; // Delete all characters
  }
  for (let j = 0; j <= n; j++) {
    dp[0][j] = j; // Insert all characters
  }
  
  // Fill DP table
  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] = Math.min(
          dp[i - 1][j] + 1,     // Delete
          dp[i][j - 1] + 1,     // Insert
          dp[i - 1][j - 1] + 1  // Replace
        );
      }
    }
  }
  
  return dp[m][n];
}

// Time: O(m * n)
// Space: O(m * n) - can optimize to O(min(m, n))

---

Common Pitfalls

• Not identifying DP: Missing overlapping subproblems. Fix: Look for recursive solutions with repeated calculations
• Wrong state definition: Storing too much or too little. Fix: Identify minimal information needed
• Incorrect transition: Wrong recurrence relation. Fix: Think about how to build current from previous
• Missing base cases: DP table not initialized. Fix: Always define base cases first
• Space inefficiency: Using O(n²) when O(n) possible. Fix: Optimize space when possible
• Not memoizing: Redundant calculations. Fix: Always cache results in memoization

---

Interview Questions

Beginner

Q: What is dynamic programming and what are its key characteristics?

A:

Dynamic Programming is an optimization technique that solves problems by:

1. Breaking into subproblems
2. Solving each subproblem once
3. Storing results to avoid recomputation

Key Characteristics:

1. Overlapping Subproblems:

Same subproblems are solved multiple times
Example: Fibonacci - fib(5) needs fib(3), fib(4) also needs fib(3)

2. Optimal Substructure:

Optimal solution contains optimal solutions to subproblems
Example: Shortest path - optimal path has optimal subpaths

Approaches:

Memoization (Top-Down):

• Start with original problem
• Recursively solve subproblems
• Cache results
• Like recursive with caching

Tabulation (Bottom-Up):

• Start with smallest subproblems
• Build up to original problem
• Fill table iteratively
• Like iterative with table

Example:

// Naive (exponential)
function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2); // Recomputes same values
}

// DP with memoization (linear)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  return memo[n];
}

---

Intermediate

Q: Explain the difference between memoization and tabulation. How do you choose between them?

A:

Memoization (Top-Down):

function dpMemo(state, memo = new Map()) {
  if (baseCase(state)) return baseValue;
  if (memo.has(state)) return memo.get(state);
  
  const result = compute(state, dpMemo);
  memo.set(state, result);
  return result;
}

Characteristics:

• Natural recursion: Fits recursive thinking
• Lazy evaluation: Only computes needed subproblems
• Stack space: Uses recursion stack
• Easier to implement: Often more intuitive

Tabulation (Bottom-Up):

function dpTab() {
  const dp = new Array(size);
  dp[0] = baseValue;
  
  for (let i = 1; i < size; i++) {
    dp[i] = compute(dp, i);
  }
  
  return dp[size - 1];
}

Characteristics:

• Iterative: No recursion overhead
• Complete table: Computes all subproblems
• Better space: Can optimize space more easily
• Faster: No function call overhead

When to use:

Use Memoization When	Use Tabulation When
Natural recursive solution	Need to optimize space
Don't need all subproblems	Need all subproblems
Hard to determine order	Clear computation order
Recursive thinking	Iterative thinking

Example - Coin Change:

Memoization:

function coinChangeMemo(coins, amount, memo = new Map()) {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  if (memo.has(amount)) return memo.get(amount);
  
  let min = Infinity;
  for (const coin of coins) {
    min = Math.min(min, 1 + coinChangeMemo(coins, amount - coin, memo));
  }
  memo.set(amount, min);
  return min;
}

Tabulation:

function coinChangeTab(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  
  return dp[amount] === Infinity ? -1 : dp[amount];
}

---

Senior

Q: Design a DP solution for a complex optimization problem: finding the maximum profit from buying and selling stocks with transaction fees and cooldown periods. How do you handle multiple states and optimize space?

A:

class StockTradingDP {
  // Problem: Buy/sell stocks with:
  // - Transaction fee per trade
  // - Cooldown period after selling
  
  maxProfit(prices: number[], fee: number, cooldown: number): number {
    const n = prices.length;
    
    // State: dp[i][state]
    // state: 0 = can buy, 1 = holding stock, 2 = cooldown
    const dp: number[][] = Array(n + 1).fill(null).map(() => Array(3).fill(0));
    
    dp[0][0] = 0;      // Start with no stock, can buy
    dp[0][1] = -prices[0]; // Buy on day 0
    dp[0][2] = -Infinity;   // Can't be in cooldown initially
    
    for (let i = 1; i < n; i++) {
      // State 0: Can buy (from cooldown or previous can-buy)
      dp[i][0] = Math.max(
        dp[i - 1][0],           // Don't buy
        dp[i - 1][2]            // Come from cooldown
      );
      
      // State 1: Holding stock (buy today or keep holding)
      dp[i][1] = Math.max(
        dp[i - 1][0] - prices[i], // Buy today
        dp[i - 1][1]              // Keep holding
      );
      
      // State 2: Cooldown (sold yesterday)
      dp[i][2] = dp[i - 1][1] + prices[i] - fee; // Sell and pay fee
    }
    
    return Math.max(dp[n - 1][0], dp[n - 1][2]);
  }
  
  // Space optimized
  maxProfitOptimized(prices: number[], fee: number, cooldown: number): number {
    let canBuy = 0;
    let holding = -prices[0];
    let cooldownState = -Infinity;
    
    for (let i = 1; i < prices.length; i++) {
      const prevCanBuy = canBuy;
      const prevHolding = holding;
      const prevCooldown = cooldownState;
      
      canBuy = Math.max(prevCanBuy, prevCooldown);
      holding = Math.max(prevCanBuy - prices[i], prevHolding);
      cooldownState = prevHolding + prices[i] - fee;
    }
    
    return Math.max(canBuy, cooldownState);
  }
  
  // With multiple transactions allowed
  maxProfitMultipleTransactions(prices: number[], fee: number): number {
    let cash = 0;        // Not holding stock
    let hold = -prices[0]; // Holding stock
    
    for (let i = 1; i < prices.length; i++) {
      // Either keep cash or sell (if holding)
      cash = Math.max(cash, hold + prices[i] - fee);
      // Either keep holding or buy (if have cash)
      hold = Math.max(hold, cash - prices[i]);
    }
    
    return cash;
  }
  
  // With at most k transactions
  maxProfitKTransactions(prices: number[], k: number): number {
    if (k === 0 || prices.length === 0) return 0;
    
    // If k >= n/2, can do unlimited transactions
    if (k >= prices.length / 2) {
      return this.maxProfitUnlimited(prices);
    }
    
    // dp[i][j][0] = max profit with i transactions, j days, not holding
    // dp[i][j][1] = max profit with i transactions, j days, holding
    const dp: number[][][] = Array(k + 1)
      .fill(null)
      .map(() => Array(prices.length)
        .fill(null)
        .map(() => Array(2).fill(0)));
    
    // Initialize
    for (let i = 0; i <= k; i++) {
      dp[i][0][1] = -prices[0]; // Buy on day 0
    }
    
    for (let i = 1; i <= k; i++) {
      for (let j = 1; j < prices.length; j++) {
        // Not holding: either keep not holding or sell
        dp[i][j][0] = Math.max(
          dp[i][j - 1][0],
          dp[i][j - 1][1] + prices[j]
        );
        
        // Holding: either keep holding or buy
        dp[i][j][1] = Math.max(
          dp[i][j - 1][1],
          dp[i - 1][j - 1][0] - prices[j]
        );
      }
    }
    
    return dp[k][prices.length - 1][0];
  }
  
  private maxProfitUnlimited(prices: number[]): number {
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
      if (prices[i] > prices[i - 1]) {
        profit += prices[i] - prices[i - 1];
      }
    }
    return profit;
  }
}

Key DP Patterns:

1. State definition: What information to track (holding/not holding, transactions left)
2. State transitions: How states change (buy, sell, hold)
3. Base cases: Initial states
4. Space optimization: Reduce dimensions when possible

---

Key Takeaways

• Dynamic programming: Optimize by storing subproblem results
• Overlapping subproblems: Same subproblems solved multiple times
• Optimal substructure: Optimal solution contains optimal subproblems
• Memoization: Top-down, recursive with caching
• Tabulation: Bottom-up, iterative with table
• State definition: Critical for correct DP solution
• Space optimization: Often can reduce space complexity