Dynamic Programming: Top-Down

Dynamic Programming: Top-Down | Algoryva

Intuition

Do not redo the homework you already did

You are asked to add up a long column of figures and, halfway through, you are asked the same subtotal again. A sensible person writes the subtotal in the margin the first time and looks it up afterwards.

Dynamic programming is exactly that habit applied to recursion: when a recursive function is asked the same question twice, answer it from a notebook instead of recomputing it.

First, the naive way

Plain recursion for Fibonacci

Fibonacci numbers are defined by fib(n) = fib(n − 1) + fib(n − 2), with fib(0) = 0 and fib(1) = 1. The recursion is a direct translation of the definition.

It is correct, but look at the call tree in the next section: fib(3) is computed twice, fib(2) three times, and the repetition grows as n grows. Counting the calls makes the waste concrete.

python

calls = 0

def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(20))   # 6765
print(calls)   # 21891

Cost: Exponential: about 1.6^n calls. fib(20) already makes 21,891 calls; fib(50) would take longer than you would wait.

See it move

The call tree without memoization

Each node is one call. Count how often fib(2), fib(1) and fib(0) appear. All those repeats compute answers that were already known.

The observation

Only n + 1 different questions exist

For fib(50) the recursion only ever asks about fib(0), fib(1), … fib(50): 51 distinct questions. The exponential number of calls is the same 51 questions asked over and over.

If we store each answer the first time it is computed, every later ask is a lookup. The total work becomes one real computation per distinct question. This works whenever the function always gives the same output for the same input and the same inputs recur (overlapping subproblems).

See it move

The same tree with a notebook

Blue nodes are cache hits: they return immediately without descending. The tree shrinks from 15 calls to 9. For larger n the gap becomes astronomical.

The concept

The top-down DP recipe

Memoization is one trick, but the real skill is setting the problem up. Follow these five steps in order:

1. State: what small set of numbers identifies a subproblem? (For Fibonacci: n. For the coin problem: the remaining amount. For two strings: a pair of positions (i, j).)
2. Meaning: write one sentence saying what f(state) returns. Everything else follows from this sentence.
3. Base cases: the states whose answer is known without further calls.
4. Transition: express f(state) using f of smaller states.
5. Memoize and answer: cache results by state, and call f on the starting state.

Implementation

Adding the notebook

Two ways. First by hand with a dictionary; you see exactly what happens.

Plan in plain steps

pseudocode

fib(n):
    if n <= 1: return n            # base case
    if n in memo: return memo[n]    # already computed
    memo[n] = fib(n-1) + fib(n-2)   # compute once, store
    return memo[n]

python

calls = 0
memo = {}

def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

(())   
(calls)

Implementation

The one-line version: `lru_cache`

Python can do the bookkeeping for you. functools.lru_cache wraps a function and stores results by its arguments. The arguments must be hashable (numbers, strings, tuples), not lists.

python

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n <= 1 else fib(n - 1) + fib(n - 2)

print(fib(50))   # 12586269025
print(fib.cache_info().misses)   # 51

Reading the code

›maxsize=None means never evict, which is what DP wants.
›misses counts how many real computations happened: exactly 51, one for each state 0..50. Everything else was a hit.
›Recursion depth is still n, so for very large n (about 1000 in Python) you need a bigger recursion limit or the bottom-up form from the next lesson.

Worked by hand

Defining state and transition for coin change

Problem: fewest coins from [1, 5, 10, 25] that sum to 63. Follow the recipe on paper before any code.

1
State
rem: how much money is still to be paid. The number of different states is at most 64 (0 to 63).
2
Meaning
go(rem) = the fewest coins needed to pay exactly rem.
3
Base cases
go(0) = 0: nothing left to pay needs no coins.
4
Transition
Try each coin c ≤ rem as the next coin: go(rem) = 1 + min(go(rem − c)) over all such c. If no coin fits, the answer is ∞ (impossible).
5
Cost estimate
At most 63 states × 4 coins = about 250 steps, versus a recursion tree that would branch 4 ways at each level.

Implementation

Minimum coins, top-down

Direct translation of the five steps.

python

from functools import lru_cache

def min_coins(coins, amount):
    @lru_cache(maxsize=None)
    def go(rem):
        if rem == 0:
            return 0
        best = float("inf")
        for c in coins:
            if c <= rem:
                best = min(best, 1 + go(rem - c))
        return best
    ans = go(amount)
    return -1 if ans == float("inf") else ans

print(min_coins((1, 5, 10, 25), 63))   # 6
print(min_coins((5, ), ))

See it move

Two-dimensional states: a table of subproblems

When a state has two numbers (a position in each of two strings), the subproblems form a grid. Here the cell in row i, column j holds the LCS length of the first i letters and the first j letters. Yellow cells are the ones the current cell depends on. The top-down version below defines the same subproblems from the other end of the strings, but the table shows the key idea: every cell depends only on neighbours, and each is computed once.

Implementation

Longest common subsequence, top-down

A subsequence keeps the order of letters but may skip some. The LCS of ABCB and BDCAB is BCB (length 3). State: (i, j), meaning the suffixes s[i:] and t[j:].

python

from functools import lru_cache

def lcs(s, t):
    @lru_cache(maxsize=None)
    def go(i, j):
        if i == len(s) or j == len(t):
            return 0
        if s[i] == t[j]:
            return 1 + go(i + 1, j + 1)
        return max(go(i + 1, j), go(i, j + 1))
    return go(0, 0)

print(lcs("ABCB", "BDCAB"))   
((, ))

Complexity

Counting the cost of a DP

One rule covers every DP: time = (number of distinct states) × (work per state). Space is the cache size plus the recursion depth.

Fibonacci, memoized

time O(n)space O(n)

n + 1 states, O(1) work each. The recursion is n deep.

Min coins

time O(amount × coins)space O(amount)

amount + 1 states, each tries every coin.

LCS

time O(n × m)space O(n × m)

(n + 1) × (m + 1) states, O(1) each.

Same problems, no memoization

time exponentialspace O(depth)

The same states are recomputed many times.

Edge cases

Unreachable states (coin change)Return infinity, not 0 or -1, inside the recursion, and convert to -1 only at the very end.
Unhashable argumentslru_cache needs hashable arguments. Pass indices or tuples instead of lists.
Deep recursionDepth can equal the state count. Raise the limit with sys.setrecursionlimit or switch to a bottom-up loop (next lesson).
Empty inputsMake sure the base case handles zero-length strings or zero amount.
State that does not capture everythingIf the answer depends on something not in the state, caching returns wrong answers. Add it to the state.
Leftover cache between test casesClear the cache (go.cache_clear()) or define go inside the function per case.

Common mistakes

Mistakes to avoid

Memoizing a function whose result depends on hidden state (globals that change).
A cached function must be pure: the same arguments always give the same result.
Putting too much in the state.
Every extra number multiplies the state count. Keep only what the answer truly depends on.
Putting too little in the state.
If two situations with the same state need different answers, the state is missing information.
Forgetting base cases, or returning the wrong value for impossible states.
Write the base cases first. For minimisation use infinity, for maximisation negative infinity, for counting 0.
Assuming greedy works because it worked on the example.
Test with a counterexample (coins 1, 3, 4 and amount 6: greedy gives 4 + 1 + 1, DP gives 3 + 3).

Recognize it in a contest

How to spot a DP problem

Reach for it when the problem says or implies

“Count the number of ways”, “minimum cost/steps”, “maximum value” where choices at each step affect later ones.
A brute-force recursion exists, and its call tree repeats the same arguments.
The answer for a size-n problem depends on answers for smaller sizes (n − 1, n − 2, prefixes, suffixes, remaining amount).
Constraints are small in a few numeric dimensions (n up to 10^3 to 10^5, or amounts up to 10^4), hinting at a table of that size.
Two sequences or one sequence with positions: states like (i, j) or (index, remaining).

Look elsewhere when

Subproblems never repeat (plain divide and conquer, like merge sort).

Worked problem

Climbing stairs with forbidden steps

The problem

You climb n stairs taking 1 or 2 steps at a time. Some stairs are broken (you cannot stand on them). Count the ways to reach stair n from stair 0.

State: i, the stair you are on.
Meaning: ways(i) = number of ways to reach stair n starting from stair i.
Base: ways(n) = 1 (you have arrived). A broken stair contributes 0 ways.
Transition: ways(i) = ways(i + 1) + ways(i + 2).

python

from functools import lru_cache

def climb(n, broken):
    bad = set(broken)
    @lru_cache(maxsize=None)
    def ways(i):
        if i > n or i in bad:
            return 0
        if i == n:
            return 1
        return ways(i + 1) + ways(i + 2)
    return ways(0)

print(climb(, []))   
((, []))

Worked problem

Grid paths

The problem

A robot starts at the top-left of an R × C grid and may move only right or down. Some cells are blocked (#). Count the paths to the bottom-right.

State: the cell (r, c). Meaning: paths from (r, c) to the goal.
Base: out of bounds or blocked gives 0; reaching the goal gives 1.
Transition: paths from (r, c) = paths from the cell below + paths from the cell to the right.

python

from functools import lru_cache

def count_paths(grid):
    R, C = len(grid), len(grid[0])
    @lru_cache(maxsize=None)
    def go(r, c):
        if r >= R or c >= C or grid[r][c] == "#":
            return 0
        if r == R - 1 and c == C - 1:
            return 1
        return go(r + , c) + (r, c + )
     (, )

(([, , ]))   
(([, , ]))

Wrap-up

Remember this

Naive recursion can repeat the same subproblems exponentially many times.
Memoization stores each answer by its state so every distinct subproblem is computed once.
Define the state, say in words what it returns, write base cases, then the transition.
Time is the number of states times the work per state.
Use it for counting, minimising and maximising over choices; check that greedy is not enough.

Cheat sheet

Recipe: state → meaning → base cases → transition → memoize
Memoize: dict, or @lru_cache(maxsize=None) with hashable args
Time: (number of states) × (work per state)
Spot it: brute force repeats arguments; count / min / max over choices
Impossible: minimise → float('inf'); convert at the end
Limit: recursion depth ≈ state count; bottom-up avoids it

Top traps to avoid

Memoizing a function whose result depends on hidden state (globals that change).
Putting too much in the state.
Putting too little in the state.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why is naive recursive fib(n) exponential?
2.A DP has 10^4 states and each state tries 5 options. Roughly how much work is that?
3.Which is not required for memoization to be correct?
4.min_coins((1, 5, 10, 25), 63) returns 6. Which set of coins does that correspond to?
5.“Count the number of ways to reach the top, moving 1 or 2 steps” is most likely:
6.Why return float('inf') for an impossible state in a minimisation DP?
7.Memoised Fibonacci: what is f(30) with f(n) = n for n < 2, else f(n-1) + f(n-2)?
8.Ways to climb 4 stairs taking 1 or 2 steps at a time, computed top-down with memoisation. What is printed?
9.What defines a top-down dynamic programme?
10.Top-down DP where there are n subproblems, each with O(1) work: what is the total time?
11.Minimum number of coins to make 11 from [1, 2, 5], top-down with memoisation. What is printed?
12.Why can plain recursion without memoisation take exponential time here?
13.Minimum path sum from top-left to bottom-right of [[1, 3], [1, 5]], moving only right or down, computed top-down. What is printed?
14.What must a memo key capture?
15.House robber on [2, 7, 9, 3, 1] (no two adjacent houses), top-down. What is the best total?

Dynamic Programming: Top-Down

After this lesson you will be able to

Builds on

Unlocks

Do not redo the homework you already did

Plain recursion for Fibonacci

The call tree without memoization

Only n + 1 different questions exist

The same tree with a notebook

The top-down DP recipe

Adding the notebook

The one-line version: `lru_cache`

Reading the code

Defining state and transition for coin change

Minimum coins, top-down

Two-dimensional states: a table of subproblems

Longest common subsequence, top-down

Counting the cost of a DP

Edge cases

Mistakes to avoid

How to spot a DP problem

Climbing stairs with forbidden steps

Grid paths

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core30 problems

Application25 problems

Challenge2 problems

Reading the code

Reading the code

Reading the code