Why it matters
Dynamic programming (DP) has a frightening name, but it rests on one plain rule: do not solve the same small problem twice. Many of the hardest-looking programs in coding interviews come down to this rule. A brute-force solution tries every choice and takes a long time. A DP solution notices that many of those choices lead to the same smaller question, answers each smaller question once, and reuses the answer. This lesson teaches the two basic ways to do that in Python, and it gives you a short recipe you can follow on problems you have never seen before.
You do not need to know much before you start. You should be able to write a function with def, use a list and a dictionary, and read a for loop. If you can save a file as main.py and run it with python3 main.py, you can run every example here. Some examples read input. The lesson tells you what to type when you run them.
The idea from first principles
Start with a problem you can break into smaller versions of itself. Suppose you want the number of ways a frog can cross a row of lily pads, and the frog can jump one pad or two pads at a time. To reach pad 10, the frog must have come from pad 9 (one jump) or from pad 8 (two jumps). So the number of ways to reach pad 10 equals the number of ways to reach pad 9 plus the number of ways to reach pad 8. The same rule holds for every pad. The big question is answered by two smaller questions of the same kind.
This is a recursive idea. Recursive means a function calls itself on a smaller input. Every recursive function needs a base case, a small input that it answers directly without calling itself again. For the frog, the base cases are pad 1 (one way: one small jump) and pad 2 (two ways: two small jumps, or one big jump).
Here is an everyday comparison. Imagine a shop that keeps a price list. A customer asks for the total price of a large order. The clerk works out each line, adds them up, and writes each line's price in the margin of the order book. The next customer who orders the same item does not need a calculator. The clerk reads the margin. The margin is a notebook of answers already worked out. DP is the same habit applied to a program: keep a notebook of answers, and check the notebook before you work anything out.
Without the notebook, a recursive solution can be extremely slow. With the notebook, the same solution becomes fast, often going from an impossible time to a time that a computer finishes in a blink. The difference is not a better formula. The difference is that each small question is answered once.
The precise version
Two properties tell you that DP may help.
- Overlapping subproblems. The same smaller question is asked more than once while solving the big question.
- Optimal substructure. The best answer to the big question can be built from the best answers to the smaller questions.
A subproblem is one of those smaller questions. A state is the set of values that describe one subproblem. For the frog, the state is one number: the pad index. Many DP problems use one number for the state, and some use two or three. Choosing the state is the most important decision you make, and the rest of the recipe follows from it.
A recurrence is the rule that gives the answer for one state in terms of other states. For the frog, the recurrence is ways(i) = ways(i - 1) + ways(i - 2). The notation ways(i) means "the number of ways to reach pad i". The recurrence is a formula, not a program, so you can check it on paper before you write any Python.
There are two ways to turn a recurrence into code.
- Memoization (top-down). Keep the recursive function. Before the function computes a state, it checks a cache. If the answer is already in the cache, it returns it. Otherwise it computes the answer, stores it in the cache, and returns it. The word comes from "memo", a short note.
- Tabulation (bottom-up). Drop the recursion. Create a table, fill in the base cases, and then fill in every other cell in an order where each cell only reads cells that are already filled. The word "tabulation" means "making a table".
Both give the same answers. They differ in how the work is organised. Memoization is often easier to write first, because it follows the recurrence exactly. Tabulation is often faster in practice and safer for large inputs, because it avoids deep recursion. You should be able to write both.
Why plain recursion is slow
Start with the most famous example. The Fibonacci numbers begin 0, 1, 1, 2, 3, 5, 8, 13, and each number after the first two is the sum of the two numbers before it. The direct Python code is one line of logic:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Read it slowly. fib(0) is 0 and fib(1) is 1, so those are the base cases. For any larger n, the function asks two smaller questions, fib(n - 1) and fib(n - 2), and adds the answers. This matches the definition exactly, so the code is correct. The problem is the amount of work.
Look at what happens when you call fib(5). It calls fib(4) and fib(3). The call to fib(4) calls fib(3) and fib(2). So fib(3) is computed at least twice already. Keep following the calls and you find that fib(2) is computed three times and fib(1) appears five times. The calls form a tree, and the tree is wide. Draw it on paper with one box per call, and the boxes with the same label are the same question asked again.
The number of calls roughly doubles every time n grows by one. Here is the exact count for the naive method, which the next program measures. For fib(5) the count is 15 calls. For fib(25) it is 242,785 calls. For fib(50) it is more than 40 billion calls, which would take a normal laptop many hours. Yet there are only 51 different questions from fib(0) to fib(50). The waste is not in the arithmetic. The waste is in asking the same 51 questions over and over.
Here is a program that counts the calls, so you can see the growth for yourself.
The program does not read input. You should see this output.
fib(5) = 5 using 15 calls
fib(10) = 55 using 177 calls
fib(20) = 6765 using 21891 calls
fib(25) = 75025 using 242785 callsTwo lines in the program need explaining. The variable calls lives at the top level of the file, outside any function. A function can read such a variable, but it cannot change it unless you say so. The line global calls tells Python that the function means the top-level variable, not a new local one. Each call to fib adds 1 to it. The line calls = 0 resets the counter before each new measurement.
The f-string f"fib({n}) = {value}" puts the values of n and value into the text. The braces {} are replaced by the value of the expression inside them.
What happens inside: the call stack
Every time a function is called, Python sets aside a small block of memory called a frame. The frame holds the function's parameters (here, n), its local variables, and a note of where to continue when the function returns. All the frames that are active at one moment form the call stack. The top frame is the call that is running now. The frames below it are the calls waiting for an answer.
When fib(5) runs, the stack grows like this. First fib(5) is on the stack. It calls fib(4), so fib(4) sits on top of it. fib(4) calls fib(3), which sits on top. fib(3) calls fib(2), and fib(2) calls fib(1). The call fib(1) is a base case. It returns 1, its frame is removed, and then fib(2) can continue. The stack shrinks and grows as calls finish and start.
What to watch for: the deepest the stack gets is about n frames, because the chain of smaller questions has length n. The total number of calls is much larger than the depth. Depth is about memory. Total calls is about time. Memoization fixes the time problem and leaves the depth the same, which is why very large inputs can still need tabulation.
Memoization: add a notebook
Now fix the waste. Keep the recursive function, and add a notebook. In Python the natural notebook is a dictionary, which stores a value under a key. The key is n, and the value is fib(n). Before computing fib(n), check whether n is already a key. If it is, return the stored value. If it is not, compute the value the normal way, store it, and return it.
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(50))
print(fib(100))
print(len(memo))Read the check carefully. if n in memo: asks whether the key n is in the dictionary. The check does not look at the stored value, so a stored 0 counts as "already computed". You will see why that matters in the common mistakes section.
Now the time. Each n from 2 to 50 is computed once. After that, every extra call is a quick lookup. The number of real computations is about n, and each one does a constant amount of work. Time is O(n). The notation O(n) is read "order n" and means the running time grows in proportion to n. Space is also O(n): the dictionary has about n entries, and the call stack can be n deep.
The output of the program is:
12586269025
354224848179261915075
99The third line is the number of entries in the dictionary. It is 99 because the function stored an answer for each n from 2 to 100.
The next program prints a message each time it computes a value and each time it uses the notebook. This is the best way to convince yourself that the cache works.
No input is needed. The output is:
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
cached fib(2)
cached fib(3)
5Walk through it with the call stack in mind. fib(5) announces itself and calls fib(4). fib(4) calls fib(3), which calls fib(2). The call fib(2) finishes, and known[2] is stored. Back in fib(3), the second call fib(1) is a base case and returns at once. fib(3) finishes. Back in fib(4), the next call is fib(2). The notebook has it, so the message says "cached fib(2)". The same thing happens for fib(3) inside fib(5). Only four real computations happened, for values 5, 4, 3 and 2. The naive version made 15 calls.
Python also has a ready-made notebook. The functools module provides lru_cache, a decorator that wraps a function with a cache. A decorator is a line starting with @ above a def. It changes the function without changing its body.
The output is:
12586269025 CacheInfo(hits=48, misses=51, maxsize=None, currsize=51)The cache has 51 misses, one for each distinct question from 0 to 50, and 48 hits, which are the repeated questions answered from the notebook. Use lru_cache when the function is pure, which means it gives the same output for the same input and has no side effects such as printing or changing a global variable. Write the dictionary by hand when you need to control the keys or to see what is stored, as this lesson does.
Tabulation: fill a table from the bottom
Memoization still uses recursion, so very deep recursion can overflow the call stack. Python limits the depth. The limit is 1000 frames by default, and you can check it with sys.getrecursionlimit() after import sys. A call chain that is deeper than the limit stops with a RecursionError, which the common mistakes section shows. Tabulation avoids the problem entirely, because it has no recursion. Instead, it creates a list and fills it in order.
For Fibonacci the table is a list dp where dp[i] holds fib(i). The base cases are dp[0] = 0 and dp[1] = 1. Every other cell is the sum of the two cells before it. If you fill the cells from left to right, each cell reads only cells that are already filled.
A list is a row of boxes, numbered from 0. dp[3] means the box at position 3. The expression [0] * (n + 1) makes a new list with n + 1 boxes, all holding 0. Here it is for Fibonacci.
The output is:
55
354224848179261915075The loop order is the important part. range(2, n + 1) produces 2, 3, ..., n, in that order. When the loop computes dp[i], the cells dp[i - 1] and dp[i - 2] were computed in earlier steps of the same loop, so they hold the right values. If you wrote the loop backward, dp[i - 1] would still be 0 when it was read, and the answer would be wrong. This is the single most common bug in tabulation, and you will meet it again in every lesson of this module.
Here is the table for fib(0) to fib(7), written as a row. The last cell is the sum of the two cells before it, and every other cell follows the same rule.
index: 0 1 2 3 4 5 6 7
dp: 0 1 1 2 3 5 8 13Using less memory
Look again at the recurrence. dp[i] uses only dp[i - 1] and dp[i - 2]. Once dp[i] is computed, the cell dp[i - 2] is never needed again. So you do not need the whole list. Two variables are enough. This turns the space from O(n) into O(1), which means a fixed amount of memory no matter how large n is.
Python lets you update two names in one line, and the right side is fully computed before any name changes. That is what makes the next function short.
The output is:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]The expression [fib_fast(i) for i in range(11)] is a list comprehension. It builds a list by running the expression once for each i. The underscore _ in for _ in range(...) is a name for a value you do not use.
This is the form most interviewers expect when they ask you to "optimise the space". Whenever a table row depends only on the row before it, or a cell depends only on the last few cells, you can shrink the table. Look for that pattern before you write a full table. The next lessons use the same trick several times.
Choosing between memoization and tabulation
Both methods give the same answer, so the choice is about cost, clarity and risk. Here is how to decide in practice.
Choose memoization when the recurrence is hard to see as a fill order. Some problems have a state space that is sparse. Only a few of the possible states are ever reached, and a table of all of them would waste memory. A dictionary stores only the states the recursion reaches. Memoization also copies the statement of the problem closely, which makes it easier to check against the brute force. If you are unsure, write memoization first, because it is hard to get the fill order wrong when the recursion chooses it for you.
Choose tabulation when the input is large and the recursion would go deep. A chain of 100,000 calls is past Python's limit of 1000, so the recursive version stops. A loop has no such limit, because the loop does not add a frame for each step. Tabulation is also easier to shrink, because you can see which earlier rows each row reads. In an interview, the usual route is to state the memoized recurrence, then convert it to a table and mention the space saving.
Here is a rule of thumb for the cost. Memoization pays for a dictionary plus the call stack, so its memory is the number of states plus the depth. Tabulation pays for the table, and it can often drop the table to one row. Both take time proportional to the number of states times the work per state, so neither is faster in the big-O sense. The difference is in the constant factors and in the risk of a RecursionError.
The DP recipe
Writing the code is the last step. Before you write anything, work through five questions in order. This recipe works for almost every problem in this module, and it is what separates a guessed solution from a solution you can explain.
- State. What do the parameters of one subproblem mean, in words? For example: "
dp[i]is the number of ways to reach stepi." - Recurrence. How does one state come from smaller states? For example: "
dp[i] = dp[i - 1] + dp[i - 2]." - Base cases. Which smallest states can be answered directly? For example: "
dp[0] = 1anddp[1] = 1." - Order. In which order must the states be filled, so that every state you read is already known? For tabulation this is the direction of a
range. For memoization the recursion handles it. - Answer. Which state holds the final answer to the question you were asked?
Write the five answers in a comment before you write the Python. Most mistakes disappear when the state is written in words, because a wrong state is almost always visible in the sentence.
Worked example: climbing stairs
A staircase has n steps. You climb one step or two steps at a time. How many different ways are there to reach the top? For n = 3 the answers are: 1 then 1 then 1, 1 then 2, and 2 then 1. That is 3 ways.
Apply the recipe. State: dp[i] is the number of ways to reach step i. Recurrence: to reach step i, your last move was either a one-step move from step i - 1 or a two-step move from step i - 2, so dp[i] = dp[i - 1] + dp[i - 2]. Base cases: there is 1 way to reach step 1 (one single step) and 2 ways to reach step 2 (two single steps, or one double step). Order: from step 3 upward. Answer: dp[n].
The next program reads n from the input and prints the whole table, so you can see the recurrence at work. Type 5 when it asks for input.
def ways(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
for i in range(1, n + 1):
print(f"step {i}: {dp[i]} ways")
return dp[n]
n = int(input())
print("answer:", ways(n))The function input() waits for a line of text and returns it as a string. int(...) turns the string into a whole number. Type 5 and press Enter. The output is:
step 1: 1 ways
step 2: 2 ways
step 3: 3 ways
step 4: 5 ways
step 5: 8 ways
answer: 8Check the table by hand. Step 3 is dp[2] + dp[1] = 2 + 1 = 3. Step 4 is 3 + 2 = 5. Step 5 is 5 + 3 = 8. The answer for n = 5 is the last cell, 8.
Two details in the code are worth copying into your habits. The base case if n <= 2: return n covers n = 0 (answer 0), n = 1 and n = 2, which are answered directly. This matches the table of Fibonacci-like numbers, but a real staircase with no steps is often treated as 1 way. Read the problem statement and write the base case that matches it. The table has n + 1 cells, so index n is valid. A list that is one cell too short causes an IndexError, which the common mistakes section shows you.
Integers in Python do not overflow
In Java, an int holds only 32 bits, and a result that is too large wraps around silently. Python does not work that way. An int in Python grows to fit the number, so there is no fixed upper limit. The next program prints Fibonacci numbers that go past the limit of a Java int.
The output is:
n = 46 value: 1836311903
n = 47 value: 2971215073
n = 48 value: 4807526976
n = 100 value: 354224848179261915075All four values are correct. You do not need to choose a number type for DP tables in Python. Some other libraries use fixed-size integers. For example, a NumPy array with the int64 type stores 64-bit values, and it wraps around like a Java long does. If you use such an array in a DP table, the overflow rules apply again. When a problem asks for an answer "modulo 1,000,000,007", the statement says so, and you take the remainder after each addition with the % operator. That technique appears in later lessons of this module.
Common mistakes
These are the mistakes that most beginners make in their first DP program. Each one is shown with the message you will see, so you can recognise it quickly.
Mistake 1: using the stored value to check whether a state is computed. Suppose the cache check is if memo.get(n):. The method get returns None when a key is missing. When the key is present, the check looks at the stored value. If the true answer for some n is 0, Python treats it as false, so the check fails every time, and the function recomputes that value on every call. The program is slower, but it still returns the right answer. The program below calls f(10) twice. The buggy check makes the second call do all 11 calls again. The fixed check uses if n in memo:, so the second call only makes one call.
calls = 0
memo = {}
def f(n):
global calls
calls += 1
if n == 0:
return 1
if memo.get(n):
return memo[n]
memo[n] = f(n - 1) * 0
return memo[n]
print(f(10), calls)
print(f(10), calls)Running it prints 0 11 and then 0 22. The fixed version, with if n in memo:, prints 0 11 and then 0 12. The fix is to test membership with in, which asks whether the key exists, not whether the value is true.
Mistake 2: reading a table cell before it is filled. In tabulation the loop must go in an order where each cell only reads finished cells. Here is a bad loop for Fibonacci that counts down.
The output is 0 and 0, not 13 and 55. The loop starts at n and reads cells that are still 0. The program runs without any error and returns 0 for almost every input. This kind of bug is silent, which makes it dangerous. Always check the direction of the loop by tracing its first two iterations on paper.
Mistake 3: a list that is one cell too short. The table for n needs n + 1 cells, because index n must exist. If you write dp = [0] * n and then fill dp[n], Python stops the program. Run this short program, saved as main.py, to see the error.
The output is below. Python 3.11 and later also draw the ~~^^^ marks under the failing part, and older versions leave them out.
Traceback (most recent call last):
File "main.py", line 7, in <module>
print(ways(5))
~~~~^^^
File "main.py", line 3, in ways
dp[n] = 1
~~^^^
IndexError: list assignment index out of rangeRead the message from the bottom. The last line names the error type, IndexError, and the message says the index is outside the list. The lines above it form the call stack at the moment of the crash, with the newest call last. The number after line is the line in your file. The file path will differ on your machine, but the shape of the message will not. The fix is to make the list n + 1 long.
Mistake 4: a RecursionError from deep recursion. Memoized recursion for a large n can go very deep. Python stops with a message like this when the depth passes the limit of 1000 frames. The program below uses the memoized function from earlier and calls it with 5000.
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(5000))Running it ends with these lines, after many repeated lines in the middle. This output is from Python 3.14. The repeat count (996 here) and the marks under the line depend on your Python version.
File "main.py", line 9, in fib
memo[n] = fib(n - 1) + fib(n - 2)
~~~^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceededThis does not mean your recurrence is wrong. It means the chain of calls is longer than Python allows. You can raise the limit with sys.setrecursionlimit, but a higher limit can crash the interpreter on a very deep chain, so it is a poor fix. Switch to tabulation, which uses a loop, for inputs in the thousands or more.
Mistake 5: writing the recurrence before the state. If you cannot say what dp[i] means in a sentence, the recurrence will be guesswork. Many students write dp[i] = dp[i - 1] + dp[i - 2] for a problem where the true state needs two indexes. Write the state in words first, and check that the recurrence uses only states that have that exact meaning.
Debugging a DP program
When a DP program gives the wrong answer, the fastest method is to print the table. You do not need a debugger for this. Add one loop that prints the list after the table is filled, and compare each cell with the value you worked out by hand.
Suppose a friend wrote this tabulation for climbing stairs. The answer for n = 4 comes out as 8, and you expected 5.
The output is 8. Add one line that prints the list dp before the return. It prints [1, 1, 2, 4, 8]. Now compare each cell with the value you work out by hand, which is [1, 1, 2, 3, 5]. The first cell that differs is dp[3]. Its line adds dp[i - 1] to itself, when it should add dp[i - 2]. The later cells are wrong only because they read dp[3]. So the rule is: find the first wrong cell, fix the recurrence that produced it, and the rest of the table follows.
Another habit that helps is to test the smallest inputs first: n = 0, n = 1, and n = 2. Those cases exercise the base cases, which are the place where most DP bugs hide. Note that for n = 0 the table above has one cell, so dp[1] does not exist, and the code fails with an IndexError. A good debugging step is to check each small input in turn.
Variations and edge cases
Real problems rarely match the textbook exactly, so think about the edge cases before you finish.
The empty input. What is the answer for n = 0? For Fibonacci, fib(0) is 0, and the code returns it. For climbing stairs, the answer depends on the problem statement. Some versions say "there is 1 way to stay at the ground". Read the statement, and write the base case that matches it. Do not guess.
Negative input. If the statement says n is at least 0, you do not need to handle negatives. If it does not, add a check at the top that raises an error, so the bug is visible. For example, if n < 0: raise ValueError("n must be 0 or more").
The maximum input. Look up the constraint. If n can be 10^6, a list of n + 1 integers uses tens of megabytes, which is usually fine. If n can be 10^9, no table fits in memory, and the problem needs a different idea, perhaps a formula. Estimating the size of the table is a skill that interviewers test.
Changing the step sizes. Suppose you can climb 1, 2 or 3 steps. The recurrence becomes dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3], with three base cases. This is the same method with one more term. When a problem gives you a list of allowed moves, the recurrence sums over the moves. The next program does this for 4 steps.
The output is 7.
Memoization with two parameters. When the state needs two numbers, the notebook becomes a dictionary with tuple keys, such as memo[(r, c)], or a two-dimensional list. The next lessons do this many times. The principle does not change. The next program counts paths in a grid of rows and columns, moving only right or down. It uses a list of lists, where dp[r][c] is the cell in row r and column c.
The output is 6. The first row and the first column are all 1, because there is only one way to reach each of them. The list comprehension [[1] * cols for _ in range(rows)] builds a separate row for each _. Writing [[1] * cols] * rows would not work, because every row would be the same list object, and changing one cell would change it in every row.
Interview-style questions and real uses
Interviewers often start with "What is dynamic programming?" A strong answer uses the two properties and a small example. Say that DP stores answers to subproblems so each one is computed once, that memoization is top-down with a cache, and that tabulation is bottom-up with a table. Then give the Fibonacci example and its time before and after.
A common follow-up is "What is the time and space complexity of your solution?" For memoized Fibonacci the time is O(n) and the space is O(n) for the cache plus the call stack. For the two-variable version the time is O(n) and the space is O(1). Say both when you answer, because the space can be reduced even when the time cannot.
Real software uses the same idea outside interviews. A compiler remembers the type of an expression once it has worked it out. A spreadsheet recalculates only the cells whose inputs changed, which is memoization with invalidation. A route planner remembers the shortest distance to a city it has already reached. Each of these is a notebook of answers that saves repeated work. Python's standard library uses the same idea in functools.lru_cache, which you saw above.
Practice
Try these before you read the solutions. Write each program in its own main.py file and run it, or do the arithmetic on paper first.
Exercise 1 (easy). Trace ways(4) from the climbing stairs program by hand. Write the table dp[1] to dp[4].
Show the answer
dp[1] = 1, dp[2] = 2, dp[3] = 2 + 1 = 3, dp[4] = 3 + 2 = 5. The answer is 5.
Exercise 2 (easy). How many calls does the naive fib(6) make, counting the very first call? Use the formula that the number of calls equals 2 * fib(n + 1) - 1, and check it against the output of the naive program for n = 5.
Show the answer
fib(7) = 13, so the count is 2 * 13 - 1 = 25. For n = 5, fib(6) = 8 and 2 * 8 - 1 = 15, which matches the program output. So fib(6) makes 25 calls.
Exercise 3 (easy). Write the state, the recurrence and the base cases for this problem: the number of paths from the top-left cell to the bottom-right cell of a 3 by 3 grid, moving only right or down.
Show the answer
State: dp[r][c] is the number of paths to cell (r, c). Recurrence: dp[r][c] = dp[r - 1][c] + dp[r][c - 1], because a path arrives from above or from the left. Base cases: every cell in the first row and the first column has exactly 1 path. The answer is dp[2][2] = 6.
Exercise 4 (medium). Change the memoized Fibonacci so that it counts how many times each value is computed, and prints the counts at the end for fib(10). Each value should be computed exactly once.
Show the answer
Keep a list computed with 11 slots, all 0. Add 1 to computed[n] at the point where the code stores memo[n]. Run print(fib(10)) and then print(computed). The output is 55 and then [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]. Every value from 2 to 10 is computed once. The base cases 0 and 1 are never counted, because they return at once.
Exercise 5 (medium). The tabulation for Fibonacci must not read a cell before it is filled. Write the loop that computes dp[i] for i from 2 to n, and explain in one sentence why counting down would give the wrong answer.
Show the answer
The loop is for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]. Counting down reads dp[i - 1] and dp[i - 2] while they are still 0, because they have not been computed yet, so the result is wrong.
Exercise 6 (medium). Write fib_fast with two variables and show that it gives the same result as the list version for n = 0 to n = 10.
Show the answer
The function fib_fast with prev and cur gives 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 for n from 0 to 10. The list version gives the same values, because both implement the same recurrence. Check that the base cases match: n = 0 returns n, which is 0, and n = 1 returns 1.
Exercise 7 (medium). A program stores Fibonacci numbers in a list made with [0] * n, and then fills dp[n] for some n. Which error does the program give, and why?
Show the answer
It gives IndexError: list assignment index out of range. The list has indexes 0 to n - 1, so index n does not exist. The fix is to make the list with n + 1 cells.
Exercise 8 (hard). Write the recurrence for the number of ways to climb n steps when you may take 1, 2 or 3 steps at a time. State the base cases for n = 0, 1 and 2, and compute the answer for n = 4 by hand.
Show the answer
Recurrence: dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] for i at least 3. Base cases: dp[0] = 1 (one way to stand at the start), dp[1] = 1, dp[2] = 2. Then dp[3] = 2 + 1 + 1 = 4 and dp[4] = 4 + 2 + 1 = 7. The answer is 7. The program above prints the same value.
Exercise 9 (hard). Explain what a RecursionError means in terms of the call stack, and describe two ways to avoid it for a memoized function that is called with n = 100000.
Show the answer
The error means the chain of active function calls grew deeper than the limit of 1000 frames. With n = 100000, the memoized recursion goes 100000 calls deep before it returns. Two fixes: write tabulation with a for loop, which uses no recursion, or use the two-variable version, which needs no deep chain. Either one keeps the time at O(n).
What you now know
- Dynamic programming avoids repeated work by storing answers to subproblems.
- It applies when subproblems overlap and the best answer is built from best answers of smaller parts.
- Memoization keeps the recursion and adds a cache, which in Python is a dictionary or
functools.lru_cache. Tabulation fills a list from the smallest state up. - The DP recipe is: state, recurrence, base cases, order, answer.
- Check a cache with
in, not with the stored value, so that a stored 0 is not mistaken for a missing answer. - Check that a list has
n + 1cells, and that a loop reads only cells that are already filled. - When a row depends only on the last one or two values, shrink the table to two variables.