House Robber
Problem Description
You are a robber planning to rob houses along a street. Adjacent houses have security systems — robbing two adjacent houses triggers an alarm. Given an integer array nums representing money in each house, return the maximum amount you can rob without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4 (rob house 1 and 3: 1+3=4)
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12 (rob house 1,3,5: 2+9+1=12)
DE Shaw Tier 3 — LC 198. Also practice LC 213 (circular street).
Optimal O(n) O(1): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Only need prev two values.
Example Test Cases
Example 1
Input: [[1,2,3,1]]
Expected: 4
Example 2
Input: [[2,7,9,3,1]]
Expected: 12
Example 3
Input: [[1]]
Expected: 1
Example 4
Input: [[2,1,1,2]]
Expected: 4
Run your code to see the results