Dynamic Programming

Interactive Visualization

Time Complexity

Key Points

• Two approaches: memoization (top-down, recursive + cache) and tabulation (bottom-up, iterative table)
• Overlapping subproblems: the same computation recurs many times in the recursive tree
• Optimal substructure: an optimal solution is built from optimal solutions to its subproblems
• Top-down starts from the original problem and caches results; bottom-up fills a table from base cases
• Space optimization: many DP solutions only need the previous row or last few values, not the full table
• Common DP families: knapsack, sequence alignment, interval scheduling, grid traversal, string matching
• State definition is the hardest part: clearly define what dp[i] (or dp[i][j]) represents before coding
• Time complexity is typically O(number of states * work per state)

Code Examples

function fib(n, memo = {}) {
  if (n <= 1) return n
  if (memo[n] !== undefined) return memo[n]

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  return memo[n]
}

// Without memo: O(2^n) - exponential!
// fib(5) calls fib(3) twice, fib(2) three times...

// With memo: O(n) - each subproblem solved once
fib(50) // 12586269025 (instant)

// Bottom-up equivalent:
function fibTab(n) {
  if (n <= 1) return n
  let prev2 = 0, prev1 = 1
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2
    prev2 = prev1
    prev1 = curr
  }
  return prev1
}

function coinChange(coins, amount) {
  // 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] + 1 < dp[i]) {
        dp[i] = dp[i - coin] + 1
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount]
}

coinChange([1, 5, 10, 25], 30) // 2 (25 + 5)
coinChange([2], 3)              // -1 (impossible)

// State: dp[amount] = min coins for that amount
// Transition: dp[i] = min(dp[i - coin] + 1) for each coin
// Time: O(amount * coins.length)
// Space: O(amount)

function longestCommonSubsequence(text1, text2) {
  const m = text1.length
  const n = text2.length
  // dp[i][j] = LCS length 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
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }

  return dp[m][n]
}

longestCommonSubsequence('abcde', 'ace')   // 3 ('ace')
longestCommonSubsequence('abc', 'def')     // 0

// Time: O(m * n), Space: O(m * n)
// Can optimize space to O(min(m, n)) using two rows

Common Mistakes

• Not identifying the correct base cases, leading to wrong initial values in the DP table
• Using plain recursion without memoization, resulting in exponential time from redundant computation
• Writing the wrong state transition formula (e.g., forgetting to consider all choices at each step)
• Off-by-one errors in table dimensions or loop bounds when converting between 0-indexed and 1-indexed
• Returning the wrong cell from the DP table (e.g., dp[n] vs dp[n-1])

Interview Tips

• Start by identifying the subproblem: what decision is being made at each step?
• Write the brute-force recursive solution first, then add memoization, then convert to tabulation if needed
• Clearly define what dp[i] (or dp[i][j]) represents before writing any transitions
• Look for keywords: "minimum", "maximum", "count ways", "is it possible" often signal DP
• After solving, discuss space optimization: can you reduce from O(n*m) to O(n) using rolling arrays?

Practice Problems

Related Concepts