House Robber
Easy
You are a professional robber planning to rob houses along a street.
Each house has a certain amount of money, given by the integer array nums.
You cannot rob two adjacent houses, because the security systems are connected.
Given nums, return the maximum amount of money you can rob without robbing two adjacent houses.
Example 1
Input
n = 4 nums = [1, 2, 3, 1]
Output
4
Explanation
Rob house 1 and house 3:
1 + 3 = 4
You cannot rob adjacent houses.
Example 2
Input
n = 5 nums = [2, 7, 9, 3, 1]
Output
12
Explanation
Rob houses with amounts:
2 + 9 + 1 = 12
This is the maximum amount possible without robbing adjacent houses.
Constraints
1 <= nums.length <= 100
0 <= nums[i] <= 400
Hints:
Hint 1
For every house, you have two choices:
- Rob it → add its money to the best result from two houses before.
- Skip it → keep the best result from the previous house.
Hint 2
The recurrence is:
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
Auto
Loading editor...
Input
Expected Output