Problems/198. House Robber
PrevNext

198. House Robber

MediumArrayDynamic Programming

You are a thief planning to rob houses along a street. Each house has a specific amount of money stashed. However, neighboring houses have security systems installed that will automatically alert the police if two adjacent houses are broken into on the same night. Given an integer array nums representing the money stashed in each house, calculate the maximum amount of money you can steal tonight without alerting the police.

Example 1
Input: nums = [2,7,9,3,1]
Output: 12
Rob house 0 (val = 2), house 2 (val = 9), and house 4 (val = 1). Total money = 2 + 9 + 1 = 12.
Example 2
Input: nums = [1,2,3,1]
Output: 4
Rob house 0 (val = 1) and house 2 (val = 3). Total money = 1 + 3 = 4.
Example 3
Input: nums = [5]
Output: 5
There is only one house, so we must rob it to get the maximum money.
Example 4
Input: nums = [3,8]
Output: 8
With two adjacent houses, we rob the one with more money (house 1).
Visualizer
⌥

Visualizer will appear here