Dynamic programming fundamentals — LeetCode patterns

Problem

Plain recursion on some problems takes exponential time, not because the problem is hard but because the same sub-question is asked again and again. Counting ways, finding a best total or deciding whether something is possible, where every choice leaves a smaller problem of the same kind, fits this shape. Dynamic programming (DP) removes the repetition, turning exponential work into a number of steps proportional to the number of distinct sub-questions.

Signal	Pattern	Why
"Number of ways to ..."	DP that sums over the last choice	Ways to finish = the sum of ways after each possible first or last move.
"Minimum / maximum total of ..."	DP that takes a min or max over choices	The best total after a choice depends only on the state it leads to.
"Is it possible to reach / form ...?"	DP over booleans	True if any move leads to a true state.
Brute-force recursion repeats the same arguments	Memoize on those arguments	Overlapping subproblems are the defining sign.
Choices look locally best but fail	DP, not greedy	DP weighs every option; greedy commits to one without proof.

Intuition

Take the Fibonacci numbers, where each is the sum of the two before it. Written as plain recursion, fib(k) calls fib(k - 1) and fib(k - 2). Computing fib(7) makes 41 calls, yet only 8 different arguments exist: fib(1) alone is computed 13 times. For fib(30) the same recursion makes over two and a half million calls (2692537), still only 31 different questions.

Two ideas fix it, and every DP solution uses one of them. Memoization keeps the recursion and adds a cache: before computing a state, check whether you already have it. Tabulation drops the recursion and fills a table of answers in an order where everything a cell needs is already filled. They compute the same values.

Amber bars are repeated work. The diagram scrolls sideways on a narrow screen.

Mechanics

The recipe

State. What few numbers pin down a subproblem? (An index, a remaining amount, a pair of positions.) If two different histories lead to the same numbers and the future is identical, they are the same state.
Meaning. Say in one sentence what dp[state] stores, for instance "the cheapest cost to finish from here". Most wrong DPs fail here, not in the code.
Transition. Express dp[state] using states that are smaller. Try every choice available at this state and combine the results with min, max or a sum.
Base cases. The states with no smaller state: the empty input, the last cell.
Order. Fill states so that each one's dependencies come first. Recursion with a cache handles this for you; a table needs it worked out.
Answer. Which state, or which combination of states, is the question?

Top-down and bottom-up

Top-down is the brute-force recursion with @functools.cache. It computes only the states reachable from the question, and it is the easy way to get a correct solution first. Bottom-up is a loop over a table. It avoids recursion depth limits and call overhead, and lets you see when old rows can be thrown away. In Python, both are accepted; start with top-down if the order of filling is unclear.

Why it is correct

The method relies on optimal substructure: the best answer for a state is built from best answers to smaller states, because what happens after a choice depends only on the state it leads to, not on how you got there. If the future depended on the history, the history would belong in the state. The running time is then the number of states times the work per state, since each state is solved exactly once.

Why not just be greedy?

A greedy rule commits to the locally best choice and never looks back. That works only when you can prove it. DP is the safe default because it compares every choice, and its cost is the size of the state space. The triangle below is a case where greedy loses.

Circle: the cell's own number. Arrow figure: the cheapest total from it to the bottom. Blue cells are the cheapest path.

Worked example

Fibonacci, three ways. The plain recursion makes 41 calls for fib(7). With a cache it makes 13 calls and computes 6 states, still returning 13. The table 0, 1, 1, 2, 3, 5, 8, 13 gets the same value from one loop over 8 cells.

k	Calls to fib(k), plain recursion	Table cell k
0	8	0
1	13	1
2	8	1
3	5	2
4	3	3
5	2	5
6	1	8
7	1	13

Cheapest path down a triangle. From a cell you may go to the cell directly below or the one below and to the right. State: the cell. Meaning: the cheapest total from this cell to the bottom row. Transition: its own number plus the smaller of the two cells below. Base: the bottom row is its own number. The order is bottom row upward, and the answer is the top cell.

Filling from the bottom gives the arrow figures in the diagram, and the top cell holds 15. Following the smaller figure at each step recovers the path 5 then 7 then 2 then 1. A greedy walk taking the smaller of the two children each time ends at 18, because the child that looks cheaper hides a worse finish.

Implementation

from functools import cache

def fib(n):
    @cache
    def go(k):
        if k < 2:
            return k
        return go(k - 1) + go(k - 2)
    return go(n)


def min_triangle_path(triangle):
    best = list(triangle[-1])            # bottom row
    for row in reversed(triangle[:-1]):
        best = [row[j] + min(best[j], best[j + 1]) for j in range(len(row))]
    return best[0]

The triangle solution keeps only one row of answers, since each row needs just the one below it. That is the usual space trim for DP: keep as many previous rows as the transition reads.

Variations and edge cases

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Rolling variables. If dp[i] reads only the previous one or two entries, keep two variables instead of an array (as in fib_iter).
Reconstruction. To print the choice, not just its value, keep the table and walk it forward, or store the chosen move beside each value.
Dictionary state. If a state is not a small integer (a tuple, a string), memoize on a dictionary; @cache does so for you.
Recursion depth. Top-down on a long input can exceed Python's recursion limit (1000 by default). Go bottom-up, or raise the limit.
Mutable arguments. Never memoize on a list; convert to a tuple or use indices.
Edge cases: empty input, a single element, and the base cases written for the wrong offset, which is the most common slip.

Complexity and tradeoffs

Time: the number of states times the work to evaluate one. Fibonacci has n states with O(1) work, so O(n); the triangle has about n²/2 states, also O(1) each.
Space: the table, or the cache; often reducible to the last few rows or entries.
Baseline. The unmemoized recursion is exponential here: 41 calls for n = 7, roughly 1.6 times more for each step up.
When it fails. If the number of states is itself enormous (values up to a billion, or subsets of many items), the table is too big. Look for a greedy proof, a closed form or a smaller state. If the future depends on the whole history, the state is not capturing it.

Problems

No list problem has this page as its home, because it supplies the method. The problems listed below use the same recipe: Climbing Stairs, House Robber and Decode Ways in the linear DP page, Coin Change as knapsack, and Longest Common Subsequence, Edit Distance and Regular Expression Matching as string DP. Each is one use of "name the state, write the transition, fill in order".

No list problem has this page as its home: it teaches the vocabulary every other page uses.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

Connections

Read first

Recursion and the call stack intro

Check yourself

Why does plain recursion for Fibonacci take exponential time?

The same sub-calls repeat. For fib(7), fib(1) alone is called 13 times, and the total is 41 calls for 8 distinct arguments.

What makes a state sufficient?

Two histories that reach the same state must have exactly the same set of possible futures and the same best future value. If something from the history changes the future, that thing belongs in the state.

On the triangle, why does the greedy walk give 18 rather than 15?

It chooses the smaller child at each step, but a small child can lead to expensive cells below. The DP compares the cheapest finish from each child, not the child's own number.

When can you replace the table with a few variables?

When each entry reads only a fixed number of earlier entries. Fibonacci reads the last two, so two variables are enough; the triangle reads one row, so one row is enough.

References

Bellman, Dynamic Programming, Princeton University Press, 1957.
Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14 (dynamic programming; optimal substructure and overlapping subproblems).
Skiena, The Algorithm Design Manual, chapter 10 (dynamic programming).
Sedgewick and Wayne, Algorithms, section 4.4 (acyclic shortest paths): relaxing a DAG's vertices in topological order is the same move as filling a DP table in dependency order.
The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.