Skip to content
Tutorials Center
My learning

Topics

Lesson 148 of 225 ยท Dynamic Programming

Dynamic Programming

Learn dynamic programming from scratch in Python: overlapping subproblems, optimal substructure, and Fibonacci solved three ways with real call counts.

Imagine someone asks you to add 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1. You count: eight. Then they write one more + 1 at the end and ask again. You do not start counting from scratch; you say "nine", because you remember the previous answer. That is the whole spirit of dynamic programming (DP): do not solve the same subproblem twice. Remember the answer and reuse it.

DP has a reputation for being scary, but it is really two ideas stacked on recursion: break a problem into smaller copies of itself, and store each answer so every copy is solved only once. In this lesson you will see exactly why naive recursion wastes work, count the waste with real numbers, and fix it three different ways. The next lesson, Memoization vs Tabulation, turns this into a repeatable recipe.

Fibonacci: the classic trap

The Fibonacci numbers start 0, 1 and each next number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, .... The definition is already a recursive program:

TEXT
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Translate it directly and it works. But watch what happens to the calls:

TEXT
                       fib(5)
                    /          \
               fib(4)           fib(3)
              /      \          /     \
         fib(3)     fib(2)   fib(2)  fib(1)
         /    \     /   \    /   \
     fib(2) fib(1) f(1) f(0) f(1) f(0)
     /   \
  f(1)  f(0)

fib(3) is computed twice, fib(2) three times. Each of those repeated calls spawns its own subtree, so the waste compounds. Let us count the calls rather than guess.

Python Naive Fibonacci and its call count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The call count is roughly 1.6 times larger every time n goes up by one, so the running time is exponential, about O(2^n) (more precisely O(phi^n), where phi is about 1.618). Asking for fib(50) this way would take billions of calls, even though only 51 different values are involved. That is the signal that DP can help.

Two properties DP needs

DP applies when a problem has both of these properties.

1. Overlapping subproblems. The recursion keeps asking the same questions. If every recursive call were brand new (as in merge sort, where the two halves never overlap), storing answers would not help. That case is plain divide and conquer.

2. Optimal substructure. The best answer to the big problem can be built from best answers to smaller problems. Shortest paths have it: if the best route from A to C goes through B, then its A-to-B part must be the best route from A to B. The longest simple path does not have it, because the best A-to-B part may use vertices that the rest of the route needs, so the pieces interfere.

TEXT
Fibonacci:   fib(n) is built from fib(n-1) and fib(n-2)
             -> only n + 1 distinct subproblems, but exponentially many calls

DP idea:     number of distinct subproblems  x  work per subproblem
             = total running time

That last formula is how you analyse almost every DP: count the states (distinct subproblems), multiply by the cost of computing one state from the smaller ones.

Fix 1: top-down with memoization

Memoization (note the missing "r": it is like a memo, a note to self) keeps the recursive code and adds a dictionary. Before computing, look up the answer; after computing, store it.

Python Fibonacci with a memo dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers tell the story: fib(20) needs 39 calls instead of 21,891, and fib(90) needs 179 calls to produce a 19-digit number (Python integers do not overflow). Each value fib(k) is computed once; every other call is a quick lookup. Time drops from O(2^n) to O(n), and the memo plus recursion stack cost O(n) space.

Python can do the bookkeeping for you with functools.cache:

Python functools.cache does the memo for you

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

cache_info() reports how many calls were hits (answers reused) and misses (answers computed). Decorators like this are the quickest way to try DP on a recursive idea.

Fix 2: bottom-up tabulation

Memoization goes top-down: start with the big question and recurse downward. Tabulation goes bottom-up: fill a table starting from the smallest subproblems, so that when you compute table[i], everything it needs is already there. No recursion at all.

TEXT
index :  0  1  2  3  4  5  6  7
table :  0  1  1  2  3  5  8  13
              ^  ^
              table[2] = table[1] + table[0]
Python Fibonacci with a table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

One loop, 89 additions for n = 90, no recursion depth to worry about. For big inputs this matters: the default recursion limit is about 1000, so a memoized fib(5000) would crash with a RecursionError while the table version works fine.

Fix 3: shrink the table

Look closely at the loop: table[i] only needs the previous two entries. Everything older is dead weight. Keep two variables and the space drops from O(n) to O(1).

Python Fibonacci in constant space

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This "keep only what the next step needs" trick appears in almost every 1-D DP. For Fibonacci there are even O(log n) methods, see fast exponentiation and matrix power.

Approach Time Space Notes
Naive recursion O(2^n) O(n) stack repeats work
Memoization (top-down) O(n) O(n) easy to write from a recursive idea
Tabulation (bottom-up) O(n) O(n) no recursion limit issues
Rolling variables O(n) O(1) when only a few previous states matter

A second example: binomial coefficients

Fibonacci is the friendly example, so let us confirm the idea transfers. The number of ways to choose k items from n obeys Pascal's rule: either you take the last item, leaving k - 1 to choose from n - 1, or you skip it and still need k from n - 1.

TEXT
C(n, k) = C(n-1, k-1) + C(n-1, k)       C(n, 0) = C(n, n) = 1
Python Choose k from n: plain recursion versus memo

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here the states are pairs (n, k), so there are at most n * k of them, each computed with one addition. The plain version makes 369,511 calls for C(20, 10); the memoized cache holds only 120 states after all three computations above. Same pattern, same cure.

How to recognise a DP problem

Ask these questions:

  1. Can I describe the answer to the whole problem in terms of answers to smaller instances of the same problem?
  2. Do those smaller instances repeat (draw a small recursion tree and look for duplicates)?
  3. Does the problem ask for a count, a minimum, a maximum, or a yes/no ("can we reach..."), rather than all the actual solutions listed out?

Phrases like "number of ways", "minimum cost", "longest", "is it possible" are common DP signals. If a problem asks you to list every solution, you are in backtracking territory, because the output itself is exponential. And if a locally best choice always works, a greedy algorithm may be simpler; see greedy vs DP.

Common mistakes

  • Forgetting the base cases. Without fib(0) and fib(1) defined, the recursion never stops.
  • Memoizing something that is not a pure function of its arguments. If the answer also depends on a global that changes, cached answers go stale.
  • Using unhashable arguments with @cache. Lists cannot be dictionary keys; convert them to tuples.
  • Shared mutable defaults for the memo. A memo={} default argument survives between calls; sometimes handy, often a bug.
  • Assuming DP is always faster. If there are no overlapping subproblems, a memo only adds memory.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is naive recursive Fibonacci slow?

    fib(n-1) and fib(n-2) both recompute many of the same smaller values, so the number of calls grows exponentially.
  2. 2. What are the two properties a problem needs for dynamic programming to help?

    Overlap makes storing answers worthwhile, and optimal substructure lets a big answer be assembled from smaller ones.
  3. 3. How many distinct states does memoized fib(n) compute?

    Each value fib(0) through fib(n) is computed once and then looked up, giving O(n) time.
  4. 4. What is the main difference between memoization and tabulation?

    Both store each subproblem's answer once. The difference is the order: demand-driven recursion versus an explicit loop from the base cases.
  5. 5. When fib(i) only needs fib(i-1) and fib(i-2), how can space be reduced to O(1)?

    Older table entries are never read again, so two rolling variables are enough.

Summary

  • Dynamic programming = recursion + remembering answers, so each distinct subproblem is solved once.
  • It needs overlapping subproblems (repeated work) and optimal substructure (big answers built from small ones).
  • Naive Fibonacci makes an exponential number of calls; memoization, tabulation and rolling variables bring it to O(n) time, with O(n), O(n) and O(1) space respectively.
  • Running time of a DP = number of states multiplied by the work per state.
  • functools.cache gives you memoization with one line; tables avoid the recursion limit.
  • Signals: "number of ways", "minimum cost", "longest", "is it possible".

Next: Memoization vs Tabulation