📊 Dynamic Programming

The Student's Notebook Analogy

Imagine you're studying for an exam. Every time you encounter a problem like "What's 47 × 23?", you calculate it from scratch.

A smart student writes the answer in a notebook. Next time the same problem appears, they just look it up!

Dynamic Programming is computing with a notebook.

Instead of solving the same subproblem over and over, you solve it once and save the answer. When you need it again, you look it up instead of recalculating.

Why DP Matters: The Fibonacci Disaster

Without DP (Exponential Time)

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)     ← Wait, calculating fib(3) again!
fib(3) = fib(2) + fib(1)
fib(3) = fib(2) + fib(1)     ← Same work, AGAIN!
fib(2) = fib(1) + fib(0)
fib(2) = fib(1) + fib(0)     ← And AGAIN!
...

For fib(50), this does BILLIONS of unnecessary calculations!

With DP (Linear Time)

fib(0) = 0                    ← Calculate once, save
fib(1) = 1                    ← Calculate once, save
fib(2) = 0 + 1 = 1            ← Look up fib(0), fib(1)
fib(3) = 1 + 1 = 2            ← Look up fib(1), fib(2)
fib(4) = 1 + 2 = 3            ← Look up fib(2), fib(3)
fib(5) = 2 + 3 = 5            ← Look up fib(3), fib(4)

Just 6 calculations total. The notebook saves the day!

When to Use DP

A problem is good for DP when it has:

1. Overlapping Subproblems

The same smaller problems keep appearing:

Calculating fib(50):
- fib(48) appears twice
- fib(47) appears three times
- fib(46) appears five times
- ...
- fib(2) appears billions of times!

2. Optimal Substructure

A strong solution to the big problem can be built from strong solutions to smaller problems:

Shortest path A → Z:
If optimal path goes through M, then:
- A → M is also optimal
- M → Z is also optimal

You can often build a good overall solution from good pieces.

Two Approaches

Top-Down (Memoization)

Start with the big problem, break it down, save results as you go:

"I need fib(5)"
  → "I need fib(4)... and fib(3)"
    → "I need fib(3)... and fib(2)"
      → (save results as you return)
    → "fib(3)? Already in notebook! Use it."

Like naturally solving a problem and jotting down intermediate answers.

Bottom-Up (Tabulation)

Start with the smallest subproblems, build up to the answer:

fib(0) = 0  (base case)
fib(1) = 1  (base case)
fib(2) = fib(0) + fib(1) = 1
fib(3) = fib(1) + fib(2) = 2
fib(4) = fib(2) + fib(3) = 3
fib(5) = fib(3) + fib(4) = 5  ✓

Like filling out a table from the beginning.

Which to Choose?

Classic Problems Explained

1. Climbing Stairs

Problem: You want to climb n stairs. Each step, you can climb 1 or 2 stairs. How many different ways?

Think about it:

• To reach stair n, you came from stair n-1 (took 1 step) OR stair n-2 (took 2 steps)
• ways(n) = ways(n-1) + ways(n-2)

That's just Fibonacci! The notebook approach works well here.

2. Coin Change

Problem: You have coins of different denominations. What's the minimum number of coins to make a certain amount?

Example: Coins [1, 3, 4], Amount = 6

Think about it:

• To make 6, I could use:
  • A 1-coin, then make 5 (min coins for 5, plus 1)
  • A 3-coin, then make 3 (min coins for 3, plus 1)
  • A 4-coin, then make 2 (min coins for 2, plus 1)
• Pick the option that uses fewest total coins

Build the notebook:
Amount 0: 0 coins (base case)
Amount 1: 1 coin (just use 1)
Amount 2: 2 coins (1+1)
Amount 3: 1 coin (just use 3)
Amount 4: 1 coin (just use 4)
Amount 5: 2 coins (4+1 or 3+1+1, pick the smaller count)
Amount 6: 2 coins (3+3)  ← Answer!

3. Longest Common Subsequence

Problem: Find the longest subsequence common to two strings.

Example: "ABCDE" and "ACE" → LCS is "ACE" (length 3)

Think about it:

• If last characters match: LCS includes it + LCS of remaining
• If they don't match: LCS is the better of (drop char from string 1) or (drop char from string 2)

4. 0/1 Knapsack

Problem: You have items with weights and values. What's the maximum value you can carry in a bag with weight limit?

Think about it: For each item, you decide: take it or leave it?

• If you take it: value + a good value for remaining capacity
• If you leave it: a good value for the same capacity without this item
• Pick whichever gives more value

The DP Recipe

Step 1: Define the State

What information do I need to describe a subproblem?

Fibonacci: Just need n
Coin change: Need the remaining amount
Knapsack: Need remaining capacity AND which items considered

Step 2: Write the Recurrence

How does the current state relate to smaller states?

fib(n) = fib(n-1) + fib(n-2)
coins(amount) = 1 + min(coins(amount-c) for each coin c)
knapsack(i, w) = max(don't take item i, take item i)

Step 3: Identify Base Cases

What are the simplest subproblems?

fib(0) = 0, fib(1) = 1
coins(0) = 0 (no coins needed for 0)
knapsack(0, w) = 0 (no items = no value)

Step 4: Decide Order (for bottom-up)

Solve smaller subproblems before larger ones.

Step 5: Optimize Space (if needed)

If you need just the last few results, don't store everything!

For Fibonacci, you typically need just fib(n-1) and fib(n-2)
→ Use two variables instead of an array

DP vs Greedy vs Divide-and-Conquer

Key Difference

Greedy: "What looks like a good choice RIGHT NOW?"
DP: "What looks good after considering many possibilities?"

Greedy can be faster but doesn't work for every problem.
DP is thorough and can find an optimal answer when the model fits the problem.

Common DP Categories

Common Mistakes

1. Not Identifying DP Problems

Look for keywords: "minimum," "maximum," "count ways," "optimal"

2. Wrong State Definition

If your solution doesn't work, you might be missing state information.

3. Forgetting Base Cases

Make sure you handle the smallest subproblems explicitly.

4. Off-by-One Errors

Double-check array indices and loop bounds.

5. Space Overflow

Large DP tables can run out of memory. Look for space optimization opportunities.

FAQ

Q: How do I know a problem needs DP?

Look for: overlapping subproblems, optimal substructure, and keywords like "minimum," "maximum," or "count the number of ways."

Q: Memoization or tabulation?

Memoization is often easier to write (just add caching to recursion). Tabulation avoids recursion overhead and is usually faster.

Q: How do I optimize space?

If dp[i] depends on just dp[i-1] and dp[i-2], you can use two variables instead of an array. If a 2D DP depends on just the previous row, you can keep two rows.

Q: Is DP usually fast?

Not necessarily. Some problems have greedy solutions that can be faster. DP can find an optimal answer when applicable, but it may be overkill.

Q: Why is it called "dynamic" programming?

Richard Bellman coined the term. "Dynamic" sounded impressive and helped him win research funding. It has nothing to do with the algorithm being dynamic.

Summary

Dynamic Programming solves complex problems by breaking them into overlapping subproblems and remembering (caching) the results to avoid redundant work.

Key Takeaways:

• DP = recursion + memoization (or tabulation)
• Key ingredients: overlapping subproblems + optimal substructure
• Top-down: recursive with caching
• Bottom-up: iterative table filling
• Define state → write recurrence → identify base cases
• Often can optimize space from O(n) to O(1)
• Essential for optimization problems in interviews

DP turns exponential problems into polynomial ones - that's the magic of the notebook!