LeetCode 198 · 1-D DP · concept: dynamic-programming
Problem
Rob houses along a street for maximum money, but you can’t rob two adjacent houses.
[2,7,9,3,1] -> 12 (rob houses 0, 2, 4: 2+9+1)
The recurrence — take it or skip it
At house i you choose: rob it (add nums[i] to the best through i−2, since i−1 is off-limits) or skip it (keep the best through i−1). So dp[i] = max(dp[i-1], nums[i] + dp[i-2]).
Approach — two rolling variables (optimal)
def rob(nums):
prev, curr = 0, 0 # dp[i-2], dp[i-1]
for n in nums:
prev, curr = curr, max(curr, prev + n)
return currTime O(n), space O(1).
The decision structure
max(skip, rob) where “rob” must reach back two houses (not one) because of the adjacency ban. That single “reach back past the forbidden neighbor” is what distinguishes this from a plain running sum, and it’s the reusable idea behind any “no two adjacent” selection problem.
Key insight
“Best subset with a no-adjacent constraint” → dp[i] = max(skip, take + dp[i-2]). The adjacency rule forces the recurrence to skip one predecessor. This exact pattern reappears in House Robber II (circular) and deletion/streak DP variants.
Related
- concept: dynamic-programming
- prev: Min Cost Climbing Stairs · next: House Robber II
Software engineering
Infrastructure & security
Computer science
Hardware & engineering