1-D dynamic programming

When to reach for it

• Counting the ways to do something along a sequence.
• The minimum or maximum over a sequence of choices: the cheapest route, the best total without taking neighbors, the fewest pieces.
• A greedy choice looks tempting, but you can build an input where it fails.
• A plain recursive solution calls itself again and again with the same arguments.

The core idea

Write three sentences before any code. The state: what dp[i] means, in words. The recurrence: how dp[i] is built from dp[i - 1], dp[i - 2] or a few other earlier states. The base cases: the answers too small to need the recurrence. Once those are right, the code is a loop.

You can go top-down, with a recursive function and a cache, or bottom-up, filling an array in order. Top-down is often the easier way to discover the recurrence; bottom-up makes the order of computation explicit and often lets you keep only the last one or two values, which brings memory down to O(1).

A Python template

from functools import lru_cache

def cheapest_climb(costs):
    """Pay costs[i] to stand on step i, move up one or two steps at a time,
    start on step 0 or 1, and finish anywhere past the last step."""
    a = b = 0                       # cheapest totals for the two previous positions
    for c in costs:
        a, b = b, c + min(a, b)     # stand here, arriving from one or two below
    return min(a, b)

def count_no_adjacent_ones(n):
    """Binary strings of length n with no two 1s next to each other."""
    @lru_cache(maxsize=None)
    def ways(i, prev_one):          # strings for positions i .. n - 1
        if i == n:
            return 1
        total = ways(i + 1, False)  # write a 0
        if not prev_one:
            total += ways(i + 1, True)  # write a 1
        return total
    return ways(0, False)

The first function is bottom-up with only two values kept. The second is top-down: the cache turns an exponential tree of calls into one call per distinct (position, last bit) pair.

Time and space

Time is the number of states times the work per state: O(n) for both examples. Space is the size of the table or cache, O(n), and drops to O(1) when each state needs only the previous one or two, as in the climbing example. Recursion adds O(n) stack depth for the top-down version.

Common mistakes

• Writing code before defining the state, then losing track of what dp[i] means halfway through.
• Wrong base cases, such as 0 where counting ways needs 1 for the empty case.
• Filling the table in an order that reads states before they are computed.
• Going greedy where it fails; find the counterexample first.
• Leaving the recursion uncached, which is exponential, and calling it dynamic programming.

How to explain it out loud

Say the state, the recurrence and the base case as three plain sentences before you type. For the climbing example: "Each value is the cheapest total to stand on a step. To stand on a step I come from one or two below, so it's its cost plus the cheaper of those. Before the first step the total is zero." This is the clearest approach planning there is, and it lets the interviewer agree with the plan before you spend time coding it.

If you start from recursion, say where it repeats work and how the cache fixes it. Trace a tiny input, give the time as states times transitions, and mention the impossible or empty case. The gap in a Devana report between explaining this and silently filling a table is usually large.