Top-down caching or bottom-up tables?

Dynamic programming Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from functools import cache


@cache
def ways(k: int) -> int:
    return 1 if k <= 1 else ways(k - 1) + ways(k - 2)


print(ways(30), ways.cache_info().currsize)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 1346269 31

Right: 31 states (0 to 30) are each computed once.

The cache size equals the number of states, which is the number the cost estimate starts from.

Why not the others?
  • B 832040 31. With ways(0) = ways(1) = 1, the value for 30 is 1346269.
  • C 1346269 2692537. The cache stores one entry per state, not per call.

30-second answer

Top-down writes the natural recursion and caches results, computing only the states actually reached; it is quickest to write but uses the call stack. Bottom-up fills a table in a fixed order with loops; it avoids recursion limits and makes memory savings like rolling rows easy. Both have the same time complexity for the same states.

Practise saying it · 45 s. No recording, just a timer

Compare top-down and bottom-up DP.

Say your answer out loud, then check which of these points you covered:

  • Same complexity
  • Top-down: quick, call stack
  • Bottom-up: loops, memory tricks

Deep dive

In Python, @functools.cache turns a recursive function into top-down DP in one line.

Top-down shines when only a fraction of states are reachable.

Bottom-up is safer for n in the tens of thousands in CPython.

Common mistakes

  • Using top-down with n = 100,000 and hitting the recursion limit.
  • Caching on a list argument, which is unhashable.

Senior take & follow-ups

Offer top-down first if it is clearer, then mention the bottom-up version and why.

Follow-up questions

Think of your answer first, then open the hint.

  1. Can you convert top-down to bottom-up mechanically?

    Show hint

    Yes: list the states in an order where dependencies come first and replace calls with table reads.

  2. Does caching change the complexity?

    Show hint

    It removes repeats, so the cost becomes states × work per state.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.