House Robber: Take-or-Skip Recurrence
Model the rob/skip decision as a DP recurrence, reduce space to two variables, and extend the solution to circular houses.
The House Robber Problem
The House Robber problem asks: given an array of non-negative integers representing the amount of money in each house, find the maximum amount you can rob without robbing two adjacent houses. For example, [2, 7, 9, 3, 1] yields 12 (rob houses 0, 2, 4). This is a classic 1D DP problem where you make a binary decision at each step.
nums = [2, 7, 9, 3, 1]
# Can't rob adjacent houses
# Options: rob index 0 and 2 and 4 → 2+9+1=12
# or rob index 1 and 3 → 7+3=10
print('Max profit:', 12) # answer is 12Defining the Recurrence
Let dp[i] be the maximum money robbed from the first i+1 houses. At each house i, you have two choices: skip it (take dp[i-1]) or rob it (take nums[i] + dp[i-2]). The recurrence is dp[i] = max(dp[i-1], nums[i] + dp[i-2]). This is the fundamental take-or-skip pattern that appears across many DP problems.
# Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# Base cases:
# dp[0] = nums[0] (only one house, rob it)
# dp[1] = max(nums[0], nums[1]) (take the richer of the two)
def rob(nums):
n = len(nums)
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
print(rob([2, 7, 9, 3, 1])) # 12All lessons in this course
- House Robber: Take-or-Skip Recurrence
- Maximum Subarray and Maximum Product Subarray
- Word Break and Segment String
- Decode Ways and Counting Paths