Patterns

Dynamic programming basics

Dynamic programming is recursion with a memory, aimed at problems that break into smaller problems of the same shape. The memory matters only when those smaller problems overlap. If every subproblem is unique, the memory buys nothing and you have written an expensive recursion. If a greedy choice is safe, the memory is also unnecessary, because you never needed to compare alternatives.

A practical way to start: write the recursive idea in a sentence, name the subproblem, then decide what you will store. "The number of ways to reach pad i" is a subproblem. "The whole input, but smarter" is not. This page uses two original examples. They are teaching problems, not a reconstructed assessment.

Counting ways that overlap

Original task: stepping stones are in a line, numbered 0 through n. From stone i you may hop to i + 1 or i + 2, if that stone exists. Return how many different hop sequences reach stone n from stone 0. Order of hops matters, so (1, 1, 2) and (2, 2) are different sequences for n equal to 4. You do not need to list them.

The overlap is easy to see for a small n. The ways to reach stone 5 include the ways to reach stone 4 followed by a hop of 1, and the ways to reach stone 3 followed by a hop of 2. Those two groups do not double-count a sequence, because the last hop differs. They do reuse the answers for 4 and 3. A recursion that does not store those answers will recompute them constantly.

def hop_sequences(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    ways_to = [0] * (n + 1)
    ways_to[0] = 1
    if n >= 1:
        ways_to[1] = 1
    for stone in range(2, n + 1):
        ways_to[stone] = ways_to[stone - 1] + ways_to[stone - 2]
    return ways_to[n]


assert hop_sequences(0) == 1
assert hop_sequences(1) == 1
assert hop_sequences(4) == 5

There is one way to stand on stone 0 without hopping: you are already there. Stone 1 is a single hop of 1. For stone 4 the five sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2. If your count disagrees, list them before you touch the code.

The loop fills each stone once, using two earlier answers. Time is linear in n. The array uses linear space. You can reduce the space to a constant by keeping only the previous two counts, because the recurrence never looks further back. Do that only after the linear version is tested. The optimized version is harder to debug and has the same time bound.

This recurrence is the Fibonacci shape. You do not need that name to use it. You need the sentence "a sequence ends in a hop of 1 or a hop of 2, and those cases are disjoint." If the hopper could also hop 3, you would add ways_to[stone - 3] once stone is at least 3. The structure of the solution would not change. That is a good sign you understood the subproblem rather than a formula.

A yes-or-no subproblem

The second example stores booleans. Original task: a list of positive task durations and a budget. Return True if some subset of the tasks sums exactly to the budget. Each task may be used once. The subset may be empty only when the budget is 0.

def can_fill_budget(durations: list[int], budget: int) -> bool:
    possible = [False] * (budget + 1)
    possible[0] = True
    for duration in durations:
        for total in range(budget, duration - 1, -1):
            if possible[total - duration]:
                possible[total] = True
    return possible[budget]


assert can_fill_budget([2, 3, 7], 5) is True
assert can_fill_budget([2, 3, 7], 1) is False
assert can_fill_budget([], 0) is True

possible[total] means "some subset sums to total." It starts true only for 0, the empty subset. Each duration is considered once. The inner loop walks totals downward so that a duration is not reused inside the same task. If you walked upward, a duration of 2 could be applied twice while you were still "on" that task, and [2] would falsely fill a budget of 4. The downward loop is the whole correctness argument. Say it in the interview. Do not treat it as a stylistic preference.

Time is proportional to the number of tasks times the budget, because each task scans the totals it might update. Space is proportional to the budget. That is a pseudo-polynomial bound: it depends on the numeric value of the budget, not only on how many tasks you were given. If the budget is huge, this array is the wrong tool, and you should say so. A meet-in-the-middle split or a different problem statement might be required. Pretending the bound is O(n) is the mistake.

The arrays and hashing prefix technique answers a different sum question: a contiguous run, not an arbitrary subset. Contiguous versus subset is the fork in the road. State it before you allocate an array. Candidates lose time building this table for a window problem, and the table is then both slower and harder to explain.

When not to use it

If a local choice never needs to be revisited, dynamic programming is a detour. The activity-selection example on the greedy page is the contrast: once you sort by finishing time, the next choice is forced, and you do not store a table of alternatives. If you find yourself filling a grid "because this seems like DP," stop and ask what the cell means. A cell without a meaning is how bugs hide.

Also skip the table when the recursion does not overlap. A recursion that splits into independent halves of a sorted array is binary search or a tree walk, not a dynamic program. Memoizing it is harmless and pointless.

Top-down memoization and bottom-up loops compute the same answers. Bottom-up is what this page coded, because the order of subproblems is obvious: increasing stone number, or increasing consideration of one more task. Top-down is pleasant when the order is awkward and you trust a cache. In an interview, pick the one you can write without mixing the two. A recursive function that also manually fills an array in a random order is how off-by-one errors multiply.

Practice drill

Implement hop_sequences with only two variables, and assert it matches the array version for n from 0 through 15. Then implement can_fill_budget and add a test where walking the inner loop upward would fail: durations [2] and budget 4 must stay false. Then change the budget function to return the number of subsets rather than a boolean. The downward loop stays. The cell becomes an integer count, and possible[0] starts at 1. If you can make that change without rereading a guide, you have the pattern.

The four-week plan puts this page late on purpose. You get more interview mileage from maps, pointers, windows, trees, and graphs. Learn this page well enough to recognize a recurrence and to reject a fake one. The common mistakes entry is using a table when a greedy choice or a single pass would do.