1D DP: Stairs and Coins

Climbing stairs

You can climb 1 or 2 steps at a time. How many different ways are there to climb n steps?

State: ways[i] = number of ways to reach step i. Transition: your last move was 1 step (from i − 1) or 2 steps (from i − 2), so ways[i] = ways[i − 1] + ways[i − 2]. Base: ways[0] = 1, ways[1] = 1.

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

print(climb(6))

Output

[1, 1, 2, 3, 5, 8, 13]

Fewest coins (where greedy fails)

State: best[a] = fewest coins to make amount a. Transition: try every coin c as the last coin: best[a] = 1 + min(best[a − c]).

def fewest_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(fewest_coins([1, 3, 4], 6))      # greedy said 3; DP finds 2 (3 + 3)
print(fewest_coins([2], 3))

Output

2
-1

Don't rob two houses in a row

Houses in a street hold some money; you can't take from two neighbours. State: best[i] = most money from the first i houses. Either skip house i (best[i − 1]) or take it (best[i − 2] + money[i]):

def rob(money):
    take, skip = 0, 0           # best so far if we took / skipped the previous house
    for m in money:
        take, skip = skip + m, max(take, skip)
    return max(take, skip)

print(rob([2, 7, 9, 3, 1]))

Output

12

Tip: When dp[i] only needs the last one or two entries, you can keep just those variables instead of the whole table: O(1) memory.