Python · Course navigation

Python dynamic programming

Reuse earlier results instead of recomputing overlapping subproblems.

On this page

Before you start

Loops, functions, and the Fibonacci recurrence.

Reuse earlier results instead of recomputing overlapping subproblems.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Fibonacci numbers satisfy F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2). Naive recursion repeats the same subproblems many times.

A bottom-up solution keeps only the two most recent values because the recurrence does not need older entries. The simultaneous assignment evaluates both right-hand values before rebinding either name.

Code example

Python

def fibonacci(n):
    if n < 0:
        raise ValueError("n must be nonnegative")
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci(6))
assert fibonacci(0) == 0
assert fibonacci(1) == 1

Output

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1def fibonacci(n):

2 if n < 0:

3 raise ValueError("n must be nonnegative")

4 a, b = 0, 1

5 for _ in range(n):

6 a, b = b, a + b

7 return a

9print(fibonacci(6))

10assert fibonacci(0) == 0

11assert fibonacci(1) == 1

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Initialize F(0) and F(1).	`a = 0, b = 1`	—
First iteration.	`a = 1, b = 1`	—
Second iteration.	`a = 1, b = 2`	—
Third iteration.	`a = 2, b = 3`	—
Fourth iteration.	`a = 3, b = 5`	—
Fifth iteration.	`a = 5, b = 8`	—
Sixth iteration.	`a = 8, b = 13`	—
Return a, which now holds F(6).	`a = 8`	8

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

O(n) additions and O(1) integer variables; the integers grow with n, so bit-level time and space are not constant.

The input contract is a nonnegative integer.
Using sequential assignments a=b then b=a+b changes the recurrence.

Try it yourself

Predict fibonacci(7) and fibonacci(8).

Reveal answer and reasoning

They are 13 and 21. Each uses the sum of the previous two results.