1D DP (climbing stairs, house robber)

One-dimensional DP problems have a single index as the state: a position on a staircase, a house on a street, a prefix of a string. dp[i] stores the best value, or the number of ways, for that prefix or position.

Climbing stairs asks how many ways you can climb n steps taking 1 or 2 at a time. The last move came from step n-1 or from step n-2, so ways(n) = ways(n-1) + ways(n-2), which is the Fibonacci recurrence.

House robber asks for the largest sum of house values you can take without taking two adjacent houses. At house i you either skip it (keep dp[i-1]) or rob it (dp[i-2] + value), so dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

1. 1Ask what the last step or last decision is: the final stair move, whether you rob the last house, how the last character is decoded.
2. 2Express dp[i] using smaller indices based on that decision: sum the options when counting ways, take max or min when optimising.
3. 3Set base cases for the smallest indices, such as ways(0) = 1 (one way to stand still) and ways(1) = 1, or robbing nothing gives 0.
4. 4Loop i from small to large, so dp[i-1] and dp[i-2] are ready when needed.
5. 5Because only the last two values are read, keep two variables instead of an array: O(n) time and O(1) space.

def climb_stairs(n):
    """Ways to climb n steps taking 1 or 2 at a time."""
    one_back, two_back = 1, 1          # ways(0) = ways(1) = 1
    for _ in range(2, n + 1):
        one_back, two_back = one_back + two_back, one_back
    return one_back


def rob(nums):
    """House robber: max sum with no two adjacent houses."""
    prev2, prev1 = 0, 0                # best up to i-2, best up to i-1
    for x in nums:
        cur = max(prev1, prev2 + x)    # skip house i, or rob it
        prev2, prev1 = prev1, cur
    return prev1

# climb_stairs(4) -> 5
# rob([2, 7, 9, 3, 1]) -> 12  (2 + 9 + 1)

Both functions read only the previous two values, so they use two variables: O(n) time and O(1) space. climb_stairs counts ways (sum), rob optimises (max).

Cost: O(n) time; O(n) space with an array, O(1) with rolling variables. Word break is O(n x L) with L the maximum word length (plus substring costs).