算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
## 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 %}