House Robber
MediumThe problem
nums[i] is the money in house i along a street. You cannot rob two houses that are next to each other. Return the most money you can rob.
- Example 1Input: nums = [1, 2, 3, 1]Output: 4
Rob house 0 and house 2: 1 + 3.
- Example 2Input: nums = [2, 7, 9, 3, 1]Output: 12
Rob houses 0, 2 and 4: 2 + 9 + 1.
Limits
- 1 ≤ len(nums) ≤ 100
- 0 ≤ nums[i] ≤ 400
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
At each house you either rob it (and skip the previous) or skip it.
The idea
dp[i] = max(dp[i−1], dp[i−2] + nums[i]); keep two variables.
Target: O(n) time, O(1) space
Go function shape
func rob(nums []int) intReference solution
Tested with go test. Try it yourself first, then compare.
// Rob: max loot from a row of houses, never two adjacent.
// State: best loot using houses[0..i]. Transition: skip house i, or take it + best up to i-2.
func Rob(nums []int) int {
take, skip := 0, 0 // best if we may use the previous house / best up to two houses ago
for _, v := range nums {
take, skip = max(skip+v, take), take
}
return take
}