What Is Dynamic Programming?

Dynamic programming (DP) is an optimization technique that solves complex problems by breaking them into smaller overlapping subproblems, solving each subproblem once, and storing the result so you never recompute it. The name sounds intimidating, but the idea is simple: remember what you've already calculated.

🧩
When does DP apply?
Two properties must hold
  • Overlapping subproblems: The same smaller problem is solved multiple times. In naive Fibonacci, fib(3) is computed again and again across different branches of the recursion tree.
  • Optimal substructure: The optimal solution to the full problem can be built from optimal solutions to its subproblems. If the shortest path from A to C goes through B, then the A-to-B segment must itself be the shortest path from A to B.
DP vs Greedy vs Divide-and-Conquer:
Greedy makes the locally best choice and never looks back. Divide-and-conquer splits the problem into independent subproblems (like merge sort). DP handles problems where subproblems overlap — the same sub-answer feeds into multiple bigger answers.

If a problem has both properties, you can solve it with DP using one of two approaches: top-down (memoization) or bottom-up (tabulation). Both give the same result — the difference is in how you traverse the subproblem space.

Visualizing the Problem: Fibonacci

Naive recursive Fibonacci is the classic example of overlapping subproblems. Let's see why fib(5) is so wasteful, and how memoization fixes it.

Naive Recursion Tree for fib(5) — Repeated Calls Highlighted in Red

f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(2) f(1) f(1) f(0) f(1) f(0) f(1) f(0)
Unique call Repeated call (wasted work) Base case

The naive tree has 15 nodes for fib(5). For fib(50) it would have over a billion. The red nodes are subproblems that get recomputed — fib(2) is solved 3 times, fib(3) is solved 2 times. That's pure waste.

Memoized Recursion — Each Subproblem Solved Only Once

f(5) f(4) f(3) memo f(3) f(2) memo f(2) f(1)
Computed once Returned from memo (O(1) lookup)

With memoization, each unique subproblem is solved exactly once. The tree collapses from exponential to linear — only n nodes for fib(n). This is the magic of DP.

Top-Down: Memoization

Memoization is the "lazy" approach: start from the top problem, recurse down, and cache results as you go. If you've already solved a subproblem, return the cached answer instead of recomputing it.

Fibonacci with @cache (Python 3.9+)

fib_cache.py O(n) time, O(n) space
Output
fib(0) = 0 fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 fib(6) = 8 fib(7) = 13 fib(8) = 21 fib(9) = 34

Fibonacci with manual memo dict

fib_memo_dict.py O(n) time, O(n) space — explicit memo
Output
12586269025
When to use top-down:
It's the most natural approach when you can write a clear recursive formula. You only solve the subproblems that are actually needed — handy when the full table is sparse. The downside: recursion depth limits (Python defaults to 1000).

Bottom-Up: Tabulation

Tabulation is the "eager" approach: start from the smallest subproblems and build up to the answer. You fill a table iteratively — no recursion, no stack overflow risk.

fib_tabulation.py O(n) time, O(n) space
Output
fib(0) = 0 fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 fib(6) = 8 fib(7) = 13 fib(8) = 21 fib(9) = 34
Top-down vs Bottom-up — which to choose?
In interviews, both are accepted. Top-down is easier to write (just add memoization to recursion). Bottom-up avoids recursion depth issues and is often faster in practice (no function call overhead). When the interviewer says "optimize", they usually mean bottom-up.

The DP Recipe: 4 Steps

Every 1D DP problem follows the same four-step process. Master this recipe and you can solve any DP problem systematically:

📋
The universal DP recipe
State → Transition → Base → Order
  1. Define the state: What does dp[i] represent? This is the most important step. For Fibonacci, dp[i] = the i-th Fibonacci number. For climbing stairs, dp[i] = number of ways to reach step i.
  2. Find the transition (recurrence): How does dp[i] relate to smaller subproblems? Fibonacci: dp[i] = dp[i-1] + dp[i-2]. This is the "aha" step — getting the recurrence right means you've essentially solved the problem.
  3. Set base cases: What are the trivially known values? Fibonacci: dp[0] = 0, dp[1] = 1. Without correct base cases, the recurrence has nothing to build on.
  4. Determine computation order: Fill the table so that when you compute dp[i], all subproblems it depends on are already solved. For 1D DP, this usually means left-to-right.

Problem: Climbing Stairs

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?

Applying the DP recipe

  • State: dp[i] = number of distinct ways to reach step i
  • Transition: dp[i] = dp[i-1] + dp[i-2] — you can arrive at step i from step i-1 (one step) or step i-2 (two steps)
  • Base cases: dp[0] = 1 (one way to stand at the ground), dp[1] = 1 (one way to reach step 1)
  • Order: Left to right, i = 2 to n
climbing_stairs.py O(n) time, O(n) space
Output
climb_stairs(2) = 2 climb_stairs(3) = 3 climb_stairs(5) = 8 climb_stairs(10) = 89
Notice something?
Climbing stairs is literally the Fibonacci sequence shifted by one index. climb_stairs(n) = fib(n+1). Recognizing familiar patterns inside new problems is a key DP skill.

Complexity: Time O(n), Space O(n). We can optimize space to O(1) — see the space optimization section below.

Problem: House Robber

You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have security systems connected — if two adjacent houses are robbed on the same night, the alarm triggers. What is the maximum amount you can rob without triggering the alarm?

Applying the DP recipe

  • State: dp[i] = maximum money you can rob from the first i houses
  • Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip house i (take dp[i-1]) or rob house i (take its value + best from two houses back)
  • Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
  • Order: Left to right, i = 2 to n-1
house_robber.py O(n) time, O(n) space
Output
4 12 4
The "skip" logic:
The key insight is that at each house you make a binary decision — rob it or skip it. If you rob house i, you can't rob house i-1, so you take the best result from house i-2 plus the current house's value. This "take or skip" pattern appears in many DP problems (knapsack, stock trading, etc.).

Problem: Coin Change (Minimum Coins)

Given an array of coin denominations and a target amount, return the fewest number of coins needed to make that amount. If it's not possible, return -1. You have unlimited coins of each denomination.

Applying the DP recipe

  • State: dp[i] = minimum coins needed to make amount i
  • Transition: dp[i] = min(dp[i - coin] + 1) for each coin where coin <= i
  • Base case: dp[0] = 0 (zero coins for amount zero)
  • Order: Left to right, i = 1 to amount
coin_change.py O(amount * len(coins)) time, O(amount) space
Output
2 2 -1

Step-by-Step Table Fill: coins = [1, 3, 4], amount = 6

Watch how the DP table fills left to right. Each cell considers all coins and picks the minimum:

Amount 0 1 2 3 4 5 6
dp[i] 0 1 2 1 1 2 2
Coins used — 1 1+1 3 4 1+4 3+3
  • dp[1] = dp[0] + 1 = 1 — use coin 1
  • dp[2] = dp[1] + 1 = 2 — use coin 1 twice
  • dp[3] = min(dp[2]+1, dp[0]+1) = min(3, 1) = 1 — use coin 3
  • dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = min(2, 2, 1) = 1 — use coin 4
  • dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = min(2, 3, 2) = 2 — use coin 4+1 or coin 1+4
  • dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3, 2, 3) = 2 — use coin 3+3
Why greedy fails here:
A greedy approach (always pick the largest coin) would pick coin 4 then coin 1 twice for amount 6 (3 coins). DP correctly finds 3+3 = 2 coins. This is exactly why DP exists — it considers all possibilities.

Space Optimization: O(n) to O(1)

When a DP recurrence only depends on the previous 1 or 2 values, you don't need the full array — just keep two variables. This is a common follow-up question in interviews.

Fibonacci / Climbing Stairs — O(1) Space

fib_optimized.py O(n) time, O(1) space
Output
fib(10) = 55 climb_stairs(10) = 89 rob([2,7,9,3,1]) = 12
When can you optimize space?
Only when dp[i] depends on a fixed number of previous entries. Fibonacci depends on dp[i-1] and dp[i-2] → two variables. Coin change depends on dp[i-coin] for any coin → you need the full array. Always check what the recurrence actually reads before optimizing.

Try It Yourself: Coin Change

Given coins [1, 5, 10, 25], find the minimum number of coins to make amount 67. Modify the code below and click Run.

Challenge Problems
Challenge 1: Decode Ways

A message containing letters A-Z is encoded where 'A' = 1, 'B' = 2, ..., 'Z' = 26. Given a string of digits, return the number of ways to decode it. For example, "226" can be decoded as "BZ" (2,26), "VF" (22,6), or "BBF" (2,2,6) — return 3.

Define dp[i] = number of ways to decode the first i characters. At each position, check if the single digit (1-9) is valid → add dp[i-1]. Then check if the two-digit number (10-26) is valid → add dp[i-2]. Base case: dp[0] = 1 (empty string has one decoding). Watch out for '0' — it can't be decoded alone.
Challenge 2: Maximum Subarray (Kadane's Algorithm)

Given an integer array, find the contiguous subarray with the largest sum and return that sum. For example, [-2, 1, -3, 4, -1, 2, 1, -5, 4] → the subarray [4, -1, 2, 1] has the largest sum = 6.

Define dp[i] = maximum subarray sum ending at index i. Transition: dp[i] = max(nums[i], dp[i-1] + nums[i]) — either start a new subarray at i, or extend the previous one. The answer is max(dp). This can be done in O(1) space with a single running variable (Kadane's algorithm).

Quiz: Dynamic Programming Basics

Question 1 of 5
What are the two properties required for a problem to be solvable with dynamic programming?
Question 2 of 5
What is the time complexity of naive recursive Fibonacci for fib(n)?
Question 3 of 5
In the House Robber problem, what does the transition dp[i] = max(dp[i-1], dp[i-2] + nums[i]) represent?
Question 4 of 5
Why does a greedy approach (always pick the largest coin) fail for Coin Change with coins [1, 3, 4] and amount 6?
Question 5 of 5
When can you optimize a DP solution from O(n) space to O(1) space?
0
/5
Great work! You understand DP basics.

Common Mistakes

  • Not identifying overlapping subproblems: If subproblems don't repeat, DP won't help — you might need divide-and-conquer or greedy instead. Check: does the same function call with the same arguments happen more than once?
  • Wrong base case: The most common DP bug. If dp[0] is wrong, every subsequent value is wrong. Always verify base cases with small examples by hand before coding.
  • Off-by-one in table size: For an amount of n, you need dp of size n + 1 (indices 0 through n). Forgetting the +1 causes an index-out-of-bounds error.
  • Forgetting to handle impossible cases: In coin change, if no combination of coins reaches the amount, dp[amount] stays at infinity. Always check for this and return -1 (or whatever the problem specifies).
  • Using mutable default arguments carelessly: The def fib(n, memo={}) trick works but the dict persists across calls. In interviews this is fine, but in production code use None as default and create the dict inside the function.

Key Takeaways

  • DP = recursion + memory. If you can write a recursive solution and see overlapping subproblems, add memoization and you have DP.
  • The 4-step recipe works every time: Define state, find transition, set base cases, determine order. Practice this on every problem until it becomes automatic.
  • Top-down and bottom-up are equivalent. Top-down (memoization) is easier to write; bottom-up (tabulation) avoids stack overflow and is usually faster. Know both.
  • Space optimization is a free follow-up win. When dp[i] only depends on dp[i-1] and dp[i-2], replace the array with two variables for O(1) space. Interviewers love this.
  • Recognize the patterns. Climbing stairs = Fibonacci. House robber = take-or-skip. Coin change = unbounded knapsack variant. Once you see 15-20 DP problems, you'll spot the pattern in seconds.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

You've learned to solve problems optimally.
Now optimize your career.

Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.

Explore our AI-era courses →