198. House Robber

Summary

Given an integer array nums, where each element represents the amount of money in a house, return the maximum amount of money you can rob tonight without alerting the police.

The alarm will automatically contact the police if two adjacent houses are broken into on the same night.

Approach

Use dynamic programming.

The maximum amount up to the i-th house is:

max(dp[i - 2] + nums[i], dp[i - 1])

At each house, you have two choices:

Rob the current house, so you add its money to the best result up to i - 2.
Skip the current house, so the best result stays the same as for i - 1.

Function

Initialization:

dp: an array initialized with zeros, of size N + 2, where N is the length of nums. Since the first house has no previous houses, adding sentinel values avoids extra boundary checks.

For each house i in nums:

dp[i + 2] = max(dp[i] + nums[i], dp[i + 1])

Return dp[-1].

Complexity

Time Complexity: O(N), where N is the number of houses. Space Complexity: O(N)