visualization

1-D DP: House Robber

Each cell asks one question: take this house, or keep yesterday's best?

nums = [2, 7, 9, 3, 1] · dp[i] = best haul from houses 0..istep 1/13

Five houses worth $2, $7, $9, $3, $1 (badges). dp[i] will hold the best haul from houses 0..i — all unknown for now.

pseudocode

dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
    skip = dp[i-1]            # best without house i
    take = dp[i-2] + nums[i]  # house i + best two back
    dp[i] = max(skip, take)
return dp[-1]