Dynamic Programming I: One Dimension

You're at the bottom of a staircase with n steps; each move climbs 1 or 2 steps. How many distinct ways to the top?

Forget efficiency. Just answer the question recursively: the last move was either a 1-step from n-1 or a 2-step from n-2, so

def ways(n):
    if n <= 1:
        return 1          # one way to stand still / take the last single step
    return ways(n - 1) + ways(n - 2)

This is correct and exponential — O(2ⁿ). Draw the call tree for ways(5) and you'll see why: ways(3) is computed twice, ways(2) three times, and the duplication snowballs. The tree has ~2ⁿ nodes but only n distinct questions ever get asked.

That gap — exponentially many calls, linearly many distinct calls — is the fingerprint of DP. The official names: overlapping subproblems (same question asked repeatedly) and optimal substructure (the answer composes from sub-answers). When both show up, you're allowed to cache.

Memoization is the laziest possible fix and it's fully legitimate: keep the recursion, but before computing, check a dictionary.

def ways(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = ways(n - 1, memo) + ways(n - 2, memo)
    return memo[n]

Each distinct n is computed once: O(n) time, O(n) space, and the code is a three-line diff from the brute force. This is top-down DP — you start from the question you care about and recurse down to base cases, caching on the way back up.

In an interview, memoization is the safest route: derive the brute force (which proves you understand the problem), then say "these calls repeat — I'll memoize." You get the optimal complexity without re-deriving anything. Its only real costs are recursion depth (Python's limit is ~1000 by default) and a bit of call overhead.

Tabulation flips the direction: instead of recursing from n down, build answers from the base cases up. Declare an array where dp[i] = number of ways to reach step i, seed the bases, and fill left to right:

def ways(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Same recurrence, no recursion, no stack-depth worries — and the access pattern is laid bare: dp[i] only ever reads the previous two slots. That observation buys the classic space squeeze:

def ways(n):
    a, b = 1, 1            # dp[i-2], dp[i-1]
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

O(n) time, O(1) space. The progression you just watched — brute recursion → memoization → tabulation → rolling variables — is the standard interview arc. You rarely need to perform all four steps, but you should be able to narrate them, because "how would you reduce the space?" is the most common DP follow-up question.

Everything else in DP is mechanical. The one creative act is answering:

"What does dp[i] mean?" — in one precise English sentence.

The default template for 1-D problems: "dp[i] = the answer for the first i elements" — or its close cousin, "the best answer for a solution ending exactly at i". Those two framings cover an enormous share of problems:

Note the "ending at" trick: when the global answer isn't naturally prefix-shaped (a subarray or subsequence can end anywhere), anchor the state to position i and take the max over all states at the end.

Write the sentence down before writing any code. If you can't state what a cell means, you can't write its recurrence — and most wrong DP solutions in interviews are wrong because the candidate skipped this sentence, not because they fumbled the loop.

Once the state sentence exists, hunt the recurrence with this checklist:

1. Stand on dp[i] and look backwards. Ask: what was the last decision that produced this state? (Last step was 1 or 2; last house robbed or skipped; last coin used was c.)
2. Enumerate the choices for that last decision. Each choice points to a smaller state. dp[i] combines them with max / min / + depending on whether you optimize or count.
3. Pin the base cases. Smallest states the recurrence can't reach — get these wrong and everything downstream is wrong. Test dp[0] and dp[1] by hand.
4. Pick a fill order in which every state is computed after the states it reads (for 1-D: usually just left to right).
5. Locate the answer. Is it dp[n], or max(dp)? ("Ending at" states need the max.)
6. Sanity-check on a tiny input — n = 3 by hand, before any code.

And the complexity, for free: time = number of states × work per state, space = number of states (until you spot a rolling-window squeeze).

Last thing: count the signals that a problem is 1-D DP at all — "number of ways", "minimum cost to reach", "longest ... ending here", choices at each index that only depend on a bounded window of earlier answers. When you hear them, say the state sentence first. Always the sentence first.