打家劫舍与动态规划总结

动态规划介绍

动态规划类似数学中的递推关系，或者更通俗地讲数列的递推关系，根据前一项与后一项之间的关系，能够推导出后一项，而一般情况下都是根据数组前面的n-1项，推导出第n项，这很有可能就是我们要求的。这种递推也可以叫做状态转移，而数组的初始值我们也可以叫做初始状态。

而打家劫舍这两题，主要是数列递推范围的问题。

打家劫舍（一）是从数组中选取最大的和，而绝对不能选取相邻的元素。

打家劫舍（二）是在上述基础上增加了首尾相连，形成了环形。

技巧

反正都是选取不相邻数字之最大和，但是因为数组有的元素可能会非常大，为了选取这个元素可能会连续舍弃掉多个附近的元素，因此不能简单地认为选取元素越多，最后结果越大，因此贪心思想在此处不可行。

对于数组每个元素，我们都有选择或是不选择两种情况，如果该处没有选择这个元素，那么到它为止拿到的元素总和就取决于它前一个元素，因为它前一个可以选；如果该处选择了这个元素，那么到它为止拿到的元素就不能考虑它前一个，只能考虑它后面一个元素。因此我们用$dp[i]dp[i]$表示到$ii$为止所能拿到的最大和，对于动态规划两个重要点：

• 初始状态： 如果数组长度为1，把这个元素拿了收益最大，因此$dp[1]=nums[0]dp[1]\; =\; nums[0]$。
• 状态转移： 每次对于一个元素，我们选择拿走或者不拿走，如果我们选择拿走那么前一个元素必定不能拿，因此累加的再前一个的最多收益，同理如果选择不拿走，那我们最多可以累加前一个元素的收益。因此转移方程为$dp[i]=max(dp[i-1],nums[i-1]+dp[i-2])dp[i]\; =\; max(dp[i\; -\; 1],\; nums[i\; -\; 1]\; +\; dp[i\; -\; 2])$。这里的i在dp中为数组长度，在nums中为下标。

不同点

• 打家劫舍（一）属于基本题，可以正常按照上述思路，动态规划转移状态得到结果。可以参考如下图：

• 打家劫舍（二）为进阶版增加了首尾不能同时选择，既然不能同时选择，我们就事先将其分开，绝不让他们有机会被同时选择。因此第一轮遍历就不用遍历到最后一位，第二轮遍历现将第一个元素置为0，两种情况选择较大值就可以了，可以参考如下图：