Dynamic Programming Explained

Dynamic programming (DP) is an algorithmic technique for solving problems by breaking them into overlapping subproblems and storing solutions to avoid redundant computation. DP is the most feared topic in interviews : but once you recognize the patterns, it becomes systematic.

When to Use DP

A problem is a DP candidate if it has:

• Optimal substructure: The optimal solution can be built from optimal solutions of subproblems.
• Overlapping subproblems: The same subproblems are solved repeatedly (brute force recomputes them).

If a recursive solution has exponential time complexity and calls the same subproblems multiple times, DP can reduce it to polynomial time.

Memoization vs Tabulation

Yellow nodes are duplicated work. Memoization eliminates these by caching results.

graph TD
    F5["fib(5)"] --> F4["fib(4)"]
    F5 --> F3["fib(3)"]
    F4 --> F3B["fib(3)"]
    F4 --> F2["fib(2)"]
    F3B --> F2B["fib(2)"]
    F3B --> F1B["fib(1)"]
    F3 --> F2C["fib(2)"]
    F3 --> F1C["fib(1)"]
    F2 --> F1D["fib(1)"]
    F2 --> F0D["fib(0)"]

    style F5 fill:#D97A2B,stroke:#B86418,color:#fff
    style F3 fill:#FFF3CD,stroke:#FFC107
    style F3B fill:#FFF3CD,stroke:#FFC107
    style F2 fill:#FFF3CD,stroke:#FFC107
    style F2B fill:#FFF3CD,stroke:#FFC107
    style F2C fill:#FFF3CD,stroke:#FFC107

Memoization (Top-Down)

Write the recursive solution first, then add a cache. Start from the main problem and work down to subproblems.

// Fibonacci : memoized
function fib(n: number, memo: Map<number, number> = new Map()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}
// Time: O(n), Space: O(n)

Tabulation (Bottom-Up)

Build the solution from the smallest subproblem up. Use an array to store results. No recursion overhead.

// Fibonacci : tabulated
function fib(n: number): number {
  if (n <= 1) return n;
  const dp = new Array(n + 1).fill(0);
  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)

Common DP Patterns

1. Knapsack

Given items with weights and values, maximize value within a weight capacity. States: (item index, remaining capacity).

2. Longest Common Subsequence

Given two strings, find the longest subsequence present in both. States: (index in string 1, index in string 2).

3. Coin Change

Given coin denominations, find the minimum coins to make a target amount. States: (remaining amount).

4. Climbing Stairs / House Robber

At each step, decide to take or skip. States: (current position). These are 1D DP problems.

Steps to Solve Any DP Problem

1. Define state: What parameters uniquely identify a subproblem?
2. Write recurrence: How does state[i] relate to previous states?
3. Base case: What are the trivial subproblems?
4. Compute order: Which states must be computed first?
5. Extract answer: Which state holds the final answer?

Common Mistakes

• Not identifying overlapping subproblems : if subproblems don't overlap, DP gives no benefit over recursion.
• Wrong state definition : the state must capture all information needed to make a decision.
• Forgetting base cases : every DP solution needs a base case to stop recursion.
• Not space-optimizing : many 2D DP problems can be reduced to 1D by only keeping the previous row.
• Starting with tabulation : start with memoization (easier to think about), then optimize to tabulation if needed.