1-D DPOne-dimensional DP

01Why it exists

Reach for it when you see:Two adjacent items cannot both be chosen, only a handful of choices at each step, the best value over the first i items, how many ways, the least cost, an answer that depends on just the last item or two, a single O(n) sweep.

02The core idea

The state of a one-dimensional DP is a single index: dp[i] is the answer when you look only at the first i items (or when you end at item i). Computing dp[i] comes down to one question — what did the last step do? The last house in House Robber is either robbed or not; the last chunk in Decode Ways is either one digit or two. Every choice shrinks the problem to a shorter prefix, and the answer for that prefix is already sitting in the table. The Memoization & Tabulation lesson wrote the recursion first and bolted a cache onto it; this lesson fills a row of cells directly, from small to large, so the work moves to defining the state and writing the transition.

Why dp[i] = max(dp[i−1], dp[i−2] + nums[i]) is correct: take any optimal plan for houses 0..i. If it leaves house i alone, it is a legal plan for houses 0..i−1 and so cannot beat dp[i−1]; if it robs house i, then house i−1 is certainly untouched and the rest is a legal plan for houses 0..i−2, so it cannot beat dp[i−2] + nums[i]. In the other direction, both of those values really are achievable. The optimum is therefore exactly the larger of the two. That is optimal substructure: strip the last step off and what remains must itself be optimal for the subproblem, or swapping in something better would contradict it. Counting problems lean on a different property — the classes must neither overlap nor miss anything. Decode Ways classifies readings by the length of the last chunk. Two readings whose last chunks have different lengths cannot be the same reading, and every reading falls into one class or the other, so adding the two counts double-counts nothing and drops nothing.

Cost: there are n states, each one looks at a fixed handful of cells and does a single O(1) max or addition, so the time is O(n). Every cell has to be filled, which makes the best and worst cases identical. The full table is O(n) space, but dp[i] only ever reads dp[i−1] and dp[i−2] — once a cell falls further behind than that it is never read again — so rolling the two variables prev2 and prev1 forward brings the space down to O(1). The price is that the table is gone: answering "which houses were robbed" means keeping it, then walking back from the last cell and checking which source each cell came from, which puts the space back at O(n). If the transition looks back k cells (30 days for the tickets, the longest word for segmentation), the time is O(nk) and the rolling version has to hold the last k cells, O(k) space.

Three mistakes come up again and again. The first is the boundary and the base cases: i−2 runs off the front when i is 0 or 1, so either fill the first two cells in advance, or give the table one extra cell and let dp[0] stand for the empty prefix. In Decode Ways the empty string has 1 reading, not 0, or everything after it comes out as 0 too. The second is the order of the rolling update: overwrite prev1 before shifting it into prev2 and what you shift across is the new value, which is why Python uses a tuple assignment and C++ parks the new value in cur first. The third is reaching for greedy instead of DP: "rob every other house" collects only 3 on [2, 1, 1, 2], where the best is 4 from the two ends. Nor does the state have to be "the first i items": Kadane's algorithm for Maximum Subarray uses "ending at item i", because a subarray has to be contiguous. When dp[i] has to look at every earlier cell (LIS) the time becomes O(n²), and when the state needs a second dimension — the remaining capacity — you are looking at the 0/1 knapsack.

03The algorithm

1. 1Write down what the state means in one sentence: is dp[i] the answer for "the first i items" or for "ending at item i"? Then settle whether the final answer is the last cell or the largest cell in the table.
2. 2Look at the last step: what choices does it have, and which smaller state does each choice fall back to? That gives you the transition. Take max for a maximum, min for a minimum, and add the classes together when counting, as long as they neither overlap nor miss anything.
3. 3Fill in the base cases: the first few cells that the transition reads but that have no source of their own. Sizing the table at n+1 and letting dp[0] stand for the empty prefix usually removes the special cases altogether.
4. 4dp[i] depends only on smaller indices, so a single loop with i going from small to large fills the whole table.
5. 5Squeeze the space: if only the previous k cells are ever read, roll k variables forward instead, and mind the update order. When you need the actual choices back, keep the whole table, check which source the last cell matches, and follow the sources backwards.

04Interactive demo

Seven houses, nums = [2, 7, 9, 3, 1, 8, 4]. Once the state is defined the two base cells go in, and after that each house takes two steps. First the two sources light up: amber is dp[i−1], the "skip it" option, and green is dp[i−2], the "rob it" option, to which the blue nums[i] still has to be added. The next step writes the larger of the two into the blue dp[i]. The prev2 and prev1 below the table are the two values the rolling version has in hand while it computes that cell. Watch i = 6: robbing gives 12 + 4 = 16, worse than the 19 you get by skipping. The final step walks back from the end, and the green houses 0, 2 and 5 are the ones that were robbed: 2 + 9 + 8 = 19.

05Code

Three functions: House Robber down to two variables, a version that keeps the whole table and walks back to recover which houses were robbed, and the counting problem Decode Ways. The first two sit side by side to show what squeezing the space costs — O(1) space leaves you the maximum and nothing else, so knowing the choices means keeping the table. The sample data is the same as in the demo.

# House Robber (LeetCode 198): no two adjacent houses, maximise the haul
# dp[i] = the most money from houses 0..i = max(dp[i-1], dp[i-2] + nums[i])
def rob(nums):
    prev2, prev1 = 0, 0                    # dp[i-2] and dp[i-1]; both 0 before any house
    for x in nums:
        # Tuple assignment: the right-hand side is evaluated from the old values, so no temp is needed
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1


# To know which houses were robbed you have to keep the whole table and walk back from the end
def rob_with_houses(nums):
    n = len(nums)
    if n == 0:
        return 0, []
    dp = [0] * n
    dp[0] = nums[0]                        # base case: one house, so rob it
    if n > 1:
        dp[1] = max(nums[0], nums[1])      # base case: two adjacent houses, take the bigger
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    houses, i = [], n - 1
    while i >= 0:
        if i == 0 or dp[i] != dp[i - 1]:   # different from the previous cell: house i had to be robbed
            houses.append(i)
            i -= 2                         # i was robbed, so i-1 was not
        else:                              # same value: house i is not needed to reach it
            i -= 1
    return dp[-1], houses[::-1]


# Decode Ways (LeetCode 91): a counting problem. "1"-"26" map to A-Z; how many readings are there?
# The last chunk is one digit or two; the two cases neither overlap nor miss anything, so add their counts
def num_decodings(s):
    prev2, prev1 = 0, 1                    # prev1 = dp[0] = 1: the empty string has one reading
    for i in range(len(s)):
        cur = 0
        if s[i] != "0":                    # on its own: 1-9
            cur += prev1
        if i > 0 and "10" <= s[i - 1:i + 1] <= "26":   # paired with the previous digit: 10-26
            cur += prev2
        prev2, prev1 = prev1, cur
    return prev1


if __name__ == "__main__":
    nums = [2, 7, 9, 3, 1, 8, 4]
    print(rob(nums))                 # 19
    print(rob_with_houses(nums))     # (19, [0, 2, 5])
    print(rob([2, 1, 1, 2]))         # 4 (robbing every other house only gives 3)
    print(num_decodings("226"))      # 3: 2-2-6, 22-6, 2-26
    print(num_decodings("2101"))     # 1: only 2-10-1
    print(num_decodings("06"))       # 0: a leading 0 cannot be decoded

06Practice

• LeetCode 198House RobberMedium
• LeetCode 740Delete and Earn (line the values up and it is House Robber)Medium
• LeetCode 213House Robber II (a ring: split into drop-the-first and drop-the-last)Medium
• LeetCode 91Decode Ways (counting, and watch out for 0)Medium
• LeetCode 139Word Break (look back by the length of each dictionary word)Medium
• LeetCode 983Minimum Cost For Tickets (look back 1, 7 and 30 days)Medium