Dynamic Programming
LC #198Medium
House Robber
Dynamic Programming
AmazonGoogleMetaMicrosoftProblem
Rob houses to maximize money without robbing two adjacent houses.
arraydynamic-programming
Constraints
- ›1 ≤ n ≤ 100
- ›0 ≤ nums[i] ≤ 400
- ›Cannot rob two adjacent houses
Example
Input
nums = [2, 7, 9, 3, 1]Output
12Why
Rob houses 0,2,4: 2+9+1=12. Or 0,2: 2+9=11. Optimal: 2+9+1=12