Dynamic Programming I: 1-D

Dynamic programming is what you use when brute-force recursion keeps solving the same smaller question. Instead of recomputing, store the answer to each subproblem once and reuse it. The speedup can be dramatic because a recursion tree collapses into a table.

The two properties you need are overlapping subproblems and optimal substructure. Overlap means the same state appears many times. Optimal substructure means the answer to a larger state can be built from answers to smaller states.

In 1-D DP, the state is usually one number: an index, an amount, a length, or a remaining capacity. The whole craft is defining that state so the recurrence becomes obvious.

The mental model

Build DP in this order:

1. State. What does dp[i] mean in one sentence?
2. Transition. Which smaller states produce dp[i]?
3. Base cases. What values are known without recursion?
4. Fill order. Do the smaller states exist before you read them?
5. Answer. Is it dp[n], max(dp), or something else?

The same recurrence can be written three ways. Start with recursion for clarity, add memoization to avoid repeats, then turn it into tabulation when the order is simple:

from functools import cache

@cache
def ways(i):
    if i <= 1:
        return 1
    return ways(i - 1) + ways(i - 2)

Bottom-up writes the states from small to large:

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]

If each state only depends on the previous one or two states, you can drop the array and keep rolling variables. Do this after the recurrence is correct, not before.

Pattern recognition

Variations

Worked problems

Try each yourself before revealing the solution. Notice how the state definition changes, but the method stays the same.

def climb_stairs(n):
    if n <= 2:
        return n

    two_back = 1
    one_back = 2

    for _ in range(3, n + 1):
        two_back, one_back = one_back, one_back + two_back

    return one_back

def rob(nums):
    two_back = 0
    one_back = 0

    for money in nums:
        current = max(one_back, two_back + money)
        two_back, one_back = one_back, current

    return one_back

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0

    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total:
                dp[total] = min(dp[total], dp[total - coin] + 1)

    return -1 if dp[amount] == float("inf") else dp[amount]

def length_of_lis(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

The state-definition pitfall

DP is overkill when every subproblem is unique, and it is unnecessary when a greedy invariant proves one choice dominates the rest. Use it when the search tree repeats itself and a compact state can remember the only history that matters.