ZERO / HERO
Climbing stairs one decision at a time

1D DP & State Design

The analogy

To reach step 10 you must have come from step 9 or step 8. So the number of ways to reach 10 is the ways to reach 9 plus the ways to reach 8. Every 1D DP is that same move: express the answer here in terms of the answers just behind you.

Visualizer

Filling one row

step 1 / 10
2
0
7
1
9
2
3
3
1
4

Houses worth [2, 7, 9, 3, 1]. You cannot rob two adjacent houses. Maximise the take.cannot rob adjacent

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

def rob(a):                       # cannot rob adjacent houses
    prev = cur = 0
    for v in a:
        prev, cur = cur, max(cur, prev + v)
    return cur

def max_subarray(a):              # Kadane: extend or restart
    best = cur = a[0]
    for v in a[1:]:
        cur = max(v, cur + v)
        best = max(best, cur)
    return best

# state: dp[i] = best answer ENDING at i
# transition looks back a FIXED distance -> O(1) space
Check yourself

Your transition scans all j < i. What is the cost, and what usually fixes it?