House Robber
House Robber is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is 1-d dynamic programming, and a good solution runs in O(n) time.
Problem
Return the maximum sum of non-adjacent non-negative house values along a street.
Examples
Example 1
Input
[3,8,4,9,2]Output
17Example 2
Input
[4,1,2,7,5,3,1]Output
14Example 3
Input
[2,1]Output
2Approach
At each house, the best total is either the best up to the previous house or this house plus the best up to two houses back.
| Pattern | 1-D dynamic programming |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
Handle zero or one house without reading out of range.