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.
- 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.
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
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
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+)
Fibonacci with manual memo dict
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.
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:
- 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. - 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. - 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. - 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 stepi - 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
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 firstihouses - 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
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 amounti - Transition:
dp[i] = min(dp[i - coin] + 1)for each coin wherecoin <= i - Base case:
dp[0] = 0(zero coins for amount zero) - Order: Left to right, i = 1 to amount
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 1dp[2] = dp[1] + 1 = 2— use coin 1 twicedp[3] = min(dp[2]+1, dp[0]+1) = min(3, 1) = 1— use coin 3dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = min(2, 2, 1) = 1— use coin 4dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = min(2, 3, 2) = 2— use coin 4+1 or coin 1+4dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3, 2, 3) = 2— use coin 3+3
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
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.
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.
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.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.
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
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 needdpof sizen + 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 useNoneas 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.
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 →