Dynamic programming has a scary name and a simple idea: don't solve the same problem twice. That one habit turns solutions that would take hours into ones that finish in milliseconds, which is why DP questions show up in almost every product-company interview and many university exams.
This is the final part of the DSA course, and it ties everything together: recursion gives you the formula, and a hash map or array remembers the answers. You'll race three approaches live, fill a DP table step by step, learn a 5-step recipe for any DP problem, and get code in Python, Java and C++.
What is dynamic programming?
If someone writes 1 + 1 + 1 + 1 + 1 on the board, you count and say 5. If they then add + 1, you instantly say 6. You didn't recount; you remembered the 5. That's dynamic programming.
A problem is a good fit for DP when it has two properties:
- Overlapping subproblems: the same smaller problem comes up again and again. In the recursion guide, fib(5) computed fib(2) three times.
- Optimal substructure: the answer to the big problem can be built from answers to smaller ones, like
fib(n) = fib(n − 1) + fib(n − 2).
See the difference: the fib(n) race
Drag the slider and compare how much work each approach does for the same answer:
🏁 The fib(n) race
Bar lengths use a log scale, otherwise the green and amber bars would be invisible. Times assume ~100 million calls a second (a fast compiled language); Python is roughly 10× slower.
At n = 20 every method feels instant. Drag the slider right.
Memoization vs tabulation
There are two ways to “write it down”. Memoization keeps your recursive code and adds a cache: before computing f(x), check if it's already stored. Tabulation drops the recursion and fills an array from the smallest case upwards.
| Feature | Memoization | Tabulation |
|---|---|---|
| Direction | Top-down: start from the big problem | Bottom-up: start from the smallest cases |
| How | Recursion + a cache (memo) | A loop that fills a table |
| Computes | Only the subproblems actually needed | Every subproblem up to n |
| Recursion depth limit? | Yes, can overflow for large n | No recursion, no limit |
| Space saving | Hard | Often easy (keep only the last row or two values) |
| Easiest to write when | You already have the recursive formula | The fill order is obvious |
Worked example: climbing stairs
You can climb 1 or 2 stairs at a time. How many different ways can you reach stair n? The key insight: to stand on stair i, your last move was either a 1-step from stair i − 1 or a 2-step from stair i − 2. So ways(i) = ways(i − 1) + ways(i − 2). Watch the table fill:
Step 1/7: Base cases: dp[0] = 1 (one way to stand at the bottom: do nothing) and dp[1] = 1 (one single step).
🧠 PATH memory card
Remember dynamic programming for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
The teacher writes 1+1+1+1+1 and you count 5. Then they add +1 and you say 6 instantly, because 5 is already written in your notebook. You never count the same thing twice.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Don't Solve Twice: Write It Down”
- Same sum again→Overlapping subproblems
- Build on the old answer→Optimal substructure
- Write It Down→Store results in a memo or table
- Look it up first→Memoization: top-down, recursion + cache
- Fill from line 1→Tabulation: bottom-up, a loop
- Don't Solve Twice→Exponential → polynomial time
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Climbing stairs, n = 5. Write the base cases: ways(0) = 1, ways(1) = 1. Then each line uses the two above it: 2, 3, 5, 8. Answer: 8 ways. Five additions instead of 15 recursive calls. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 9 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
How to solve any DP problem: a 5-step recipe
- Define the state: what does
dp[i]mean, in plain words? (“number of ways to reach stair i”) - Write the recurrence: how does
dp[i]come from smaller states? (“dp[i − 1] + dp[i − 2]”) - Set the base cases: the smallest states you can answer directly.
- Choose the order: fill so every state you need is ready first (usually small to large).
- Return the answer: which cell holds the final result (often
dp[n]).
DP code: Fibonacci, climbing stairs and coin change
All three approaches for Fibonacci, the O(1)-space climbing stairs, and the classic coin change problem.
from functools import lru_cache
# 1) Plain recursion: correct but O(2^n)
def fib_slow(n):
if n <= 1:
return n
return fib_slow(n - 1) + fib_slow(n - 2)
# 2) Memoization (top-down): recursion + cache, O(n)
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
@lru_cache(maxsize=None) # Python can memoize for you
def fib_cached(n):
return n if n <= 1 else fib_cached(n - 1) + fib_cached(n - 2)
# 3) Tabulation (bottom-up): a loop and a table, O(n)
def fib_table(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Climbing stairs (1 or 2 steps), O(n) time, O(1) space
def climb_stairs(n):
a, b = 1, 1 # ways(0), ways(1)
for _ in range(n - 1):
a, b = b, a + b
return b
# Coin change: fewest coins to make amount, O(amount * coins)
def min_coins(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount # dp[x] = fewest coins for x
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
return dp[amount] if dp[amount] != INF else -1
print(fib_memo(50)) # 12586269025 (instant)
print(fib_table(50)) # 12586269025
print(climb_stairs(6)) # 13
print(min_coins([1, 2, 5], 11)) # 3 (5 + 5 + 1)Classic DP problems to practise next
| Problem | Core idea | Level |
|---|---|---|
| Climbing stairs / Fibonacci | ways(n) = ways(n−1) + ways(n−2) | Easy |
| House robber | best(i) = max(best(i−1), best(i−2) + money[i]) | Easy |
| Coin change (fewest coins) | dp[x] = min(dp[x − coin] + 1) | Medium |
| 0/1 knapsack | take or skip each item, by remaining capacity | Medium |
| Longest common subsequence | match → 1 + diagonal; else max(up, left) | Medium |
| Edit distance | min of insert, delete, replace + 1 | Hard |
You finished the DSA course 🎉
From Big O to dynamic programming, you now know the core of what exams and interviews test. Go back to the course page to check your progress, and use the flashcards in each guide: a few minutes of review a day keeps all ten topics fresh.
Key takeaways
- ✓DP = solve each overlapping subproblem once, store it, reuse it.
- ✓It needs overlapping subproblems and optimal substructure.
- ✓Memoization: top-down recursion + cache. Tabulation: bottom-up loop + table.
- ✓Fibonacci drops from O(2ⁿ) to O(n); climbing stairs even to O(1) space.
- ✓Recipe: state, recurrence, base cases, order, answer.
- ✓Remember it with “Don't Solve Twice: Write It Down.”
Frequently asked questions
What is dynamic programming in simple words?
Dynamic programming (DP) is a way to solve a problem by breaking it into smaller overlapping subproblems, solving each subproblem only once, and storing the answer so it can be reused instead of recomputed. It turns many exponential-time recursive solutions into polynomial-time ones.
What is the difference between memoization and tabulation?
Memoization is top-down: you write the natural recursive solution and cache each result the first time you compute it. Tabulation is bottom-up: you fill a table iteratively from the smallest subproblems up to the answer, with no recursion. Both give the same time complexity; tabulation avoids recursion depth limits and often allows saving space.
How do I know if a problem can be solved with dynamic programming?
Look for two properties. Overlapping subproblems: the same smaller problem is solved again and again (like fib(3) inside fib(5)). Optimal substructure: the best answer for the whole problem can be built from the best answers of its subproblems. Words like “number of ways”, “minimum cost”, “maximum profit” and “longest” are common hints.
What is the difference between dynamic programming and recursion?
Recursion is a way of writing code (a function calling itself). Dynamic programming is an optimisation strategy: avoid repeating work by storing results. Top-down DP is recursion plus a cache; bottom-up DP doesn't use recursion at all.
What are the most common dynamic programming problems for beginners?
Fibonacci, climbing stairs, house robber, coin change (minimum coins and number of ways), 0/1 knapsack, longest common subsequence, longest increasing subsequence, edit distance and unique grid paths. Most interview DP questions are variations of these.
🧠 Quick check: dynamic programming
1. Which two properties signal that a problem fits dynamic programming?
2. What does memoization add to a plain recursive solution?
3. Climbing stairs: you can take 1 or 2 steps. If ways(3) = 3 and ways(4) = 5, what is ways(5)?
4. In the PATH anchor “Don't Solve Twice: Write It Down”, which approach fills the notebook from line 1?
Checking your access…