roadmap/Dynamic Programming

Topic 11 / 16

Dynamic Programming

HardOptimization~10 days
Very hard
progress0 / 19 solved

Cache subproblem results to avoid redundant computation. Recognize overlapping subproblems.

⚠️
Why this topic is hard

DP is hard for three reasons: (1) Recognizing that DP applies at all — the problem must have overlapping subproblems and optimal substructure. (2) Defining what dp[i] means — this definition IS the solution. Get it wrong and nothing works. (3) Getting the recurrence relation right — this requires understanding how the optimal answer to a big problem relates to answers of smaller problems. The good news: there are only ~5 DP patterns that cover 90% of interview problems.

Concept

Break the problem into overlapping subproblems. Cache results to avoid recomputation (memoization = top-down; tabulation = bottom-up). DP is applicable when: (1) the problem has overlapping subproblems, and (2) an optimal solution can be built from optimal sub-solutions (optimal substructure).

When to use this pattern
  • ◆Counting distinct ways to reach a goal
  • ◆Maximum/minimum cost path through a grid or sequence
  • ◆Longest common subsequence/substring
  • ◆0/1 Knapsack and unbounded knapsack variants
  • ◆String edit distance
Common patterns
1D DP (linear)
dp[i] depends on dp[i-1] or dp[i-2]. Fibonacci, climbing stairs.
2D DP (grid/sequence)
dp[i][j] depends on neighbors. LCS, edit distance.
Knapsack
For each item, decide include or exclude. dp[i][w].
Interval DP
dp[i][j] = best result for subarray [i, j].
Visual walkthrough
Dynamic Programming
Coin Change — dp table filling
INIT
coins =
1
3
4
target = 6
dp[0..6]
0
0
∞
1
∞
2
∞
3
∞
4
∞
5
∞
6
dp[i] = min over all coins c where c≤i: dp[i-c] + 1
Base case: dp[0] = 0
Amount 0 needs 0 coins. All others start at ∞ (impossible).
step 1/24
Brute force → optimal thinking
Brute force
Recursion with no caching — exponential recomputation.
Observation
The same subproblem is solved many times. Result depends only on a fixed set of smaller subproblems.
Optimization
Top-down: add a memo cache to the recursion. Bottom-up: fill a dp table iteratively from smallest subproblem.
Final complexity
O(n²) or O(n×m) for 2D DP. O(n) for 1D. Space often optimizable to O(1) or O(n) with rolling array.
Side-by-side: brute force vs optimized
Coin Change — Brute Force vs DP
Brute Force
// Brute Force — try every combination
// Time: O(S^n) where S = amount, n = coins
function coinChange(coins, amount) {
  function dfs(remaining) {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    
    let best = Infinity;
    for (const coin of coins) {
      // Recursively try each coin
      const result = dfs(remaining - coin);
      if (result !== Infinity) {
        best = Math.min(best, result + 1);
      }
    }
    return best;
  }
  
  const result = dfs(amount);
  return result === Infinity ? -1 : result;
}
// Problem: dfs(11) calls dfs(10) multiple times
// Each subtree is recomputed from scratch
Optimized (DP)
// DP (Bottom-Up) — build the table
// Time: O(S × n)  Space: O(S)
function coinChange(coins, amount) {
  // dp[i] = min coins needed to make amount i
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // base case: 0 coins for amount 0
  
  // Fill table from amount 1 → target
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        // Either don't use this coin: dp[i]
        // Or use it: dp[i - coin] + 1
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  
  return dp[amount] === Infinity ? -1 : dp[amount];
}
// Each subproblem computed exactly ONCE
// dp[11] reuses dp[10], dp[9], dp[6] directly
Key insight

The brute force recomputes the same subproblems exponentially. The DP version defines dp[i] = min coins for amount i, fills the table bottom-up, and each cell is computed in O(n) — total O(S×n). The mental shift: TRUST that dp[i-coin] already has the correct answer when you need it.

Quick Recall Check

What are the two key properties a problem must have for DP to apply?

In the coin change problem, what does dp[i] represent?

What is the recurrence for Longest Common Subsequence when characters match?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Graphs (DFS / BFS)
next
Greedy
→
Progress is saved on this device