## House Robber
### 描述
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight **without alerting the police**.
### 分析
这是一个多阶段最优化问题,且要走到最底部才能知道答案,因此广搜排除,只剩下贪心和动规。贪心明显要排除,只剩下动规。
设状态 `f[i]` 为到位置`i`时能抢到的金钱最大和,那么状态转移方程如下:
`f[i]=max(f[i-1], f[i-2] + nums[i])`
其含义是,如果不选择`i`,则抢到的钱是`f[i-1]`,如果选择`i`,则能抢到的钱是`f[i-2] + nums[i]`。
### 解法1
{% if book.java %}
{% codesnippet "./code/house-robber-1."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}
### 解法2
在状态转移方程中,我们可以发现 `f[i]`仅仅依赖前两项,因此用两个整数变量即可代替一位数组,将空间复杂度降为`O(1)`。
{% if book.java %}
{% codesnippet "./code/house-robber-2."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}