Dynamic Programming

A fancy name for one lazy trick: never solve the same small problem twice

Dynamic programming has a scary name. The idea behind it is not scary at all.
Here it is, in one line: never work out the same small answer twice.
Solve each little piece once. Write the answer down. The next time you need it, look it up instead of solving it again. That is the whole trick.

Let's see it on a staircase.
You are climbing stairs. You can go up 1 step or 2 steps at a time. How many different ways can you reach the top?
Think about the very top step. You landed on it from one step below, or from two steps below. So the ways to reach the top is just the ways to reach those two lower steps, added together.
The slow way works each step out again and again. The smart way writes each one down once. Drag the slider and watch the gap.

🧾In the Real World...

You already do this. When you add up a long shopping bill, you do not start from the first item every time the total grows. You keep the running total and add the next price. That is dynamic programming.

Before⚠ Works but messy

# The slow way: work it out fresh every time
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
# fib(50) would take hours

After✓ Pythonic

# The smart way: build up and remember
def fib(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
# fib(50) is instant

💡

Same answer both times. The top one re-solves the same steps over and over, so it crawls. The bottom one builds up and remembers, so it flies.

People give the "write it down" trick two names, depending on how you do it.
Solve it with recursion and keep a notepad of answers you have already seen? That is called *memoization*.
Fill in a table from the smallest answer up to the one you want? That is called *tabulation*.
Do not let the words worry you. They are two ways to do the same thing: remember, so you never repeat work.

Memoization: recursion plus a notepadpython

from functools import lru_cache

# lru_cache is the notepad. It remembers every answer.
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

print(fib(50))  # 12586269025, and it is instant

🤔Quick Check

Why does writing each answer down make it so much faster?

🤔Quick Check

When is the "write it down" trick actually worth it?

Practice Exercises

0/1 solved

Exercise 1 of 1easy

⏱ 00:00

Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways to reach the top of n stairs?
Expected output: 8

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next