DP 第六讲 - 打家劫舍

在前两篇中，我们分别学习了 “三角形最小路径和” 以及“矩形最小路径和” 的问题，相信已经掌握了这类题型的解题方式。我们只要明确状态的定义，基本上都可以顺利求解。


在本节中，我们将回归一道简单点的题目，目的是剖析一下状态定义的过程，并且举例说明如果状态定义错误，会对我们带来多大困扰！希望大家不要轻视！

01、题目分析

第198题：打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

  1. 输入: [1,2,3,1]
  2. 输出: 4
  3. 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
  4.      偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

  1. 输入: [2,7,9,3,1]
  2. 输出: 12
  3. 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
  4.      偷窃到的最高金额 = 2 + 9 + 1 = 12 。


本题主要剖析状态定义的过程！强烈建议先进行前面5节内容的学习！

以达到最好的学习效果！

02、题目图解

假设有i间房子，我们可能会定义出两种状态：

  • dp[i] : 偷盗 含 第 i个房子时，所获取的最大利益
  • dp[i] : 偷盗 至 第 i个房子时，所获取的最大利益


如果我们定义为状态一，因为我们没办法知道获取最高金额时，小偷到底偷盗了哪些房屋。所以我们需要找到所有状态中的最大值，才能找到我们的最终答案。即：

max(dp[0],dp[1],…..,dp[len(dp)-1])

如果我们定义为状态二，因为小偷一定会从前偷到最后（强调：偷盗至第i个房间，不代表小偷要从第i个房间中获取财物）。所以我们的最终答案很容易确定。即：

dp[i]

现在我们分析这两种状态定义下的状态转移方程：


如果是状态一，偷盗含第 i 个房间时能获取的最高金额，我们相当于要找到偷盗每一间房子时可以获取到的最大金额。比如下图，我们要找到 dp[4] ，也就是偷盗 9 这间房子时，能获取到的最大金额。

PNG

那我们就需要找到与9不相邻的前后两段中能获取到的最大金额。

PNG

我们发现题目进入恶性循环，因为我们若要找到与9不相邻的两端中能偷盗的最大金额，根据 dp[i] 的定义，我们就又需要分析在这两段中盗取每一间房子时所能获取的最大利益！想想都很可怕！所以我们放弃掉这种状态的定义。


如果是状态二，偷盗至第 i 个房子时，所能获取的最大利益。那我们可以想到，由于不可以在相邻的房屋闯入，所以 至i房屋可盗窃的最大值，要么就是至 i-1 房屋可盗窃的最大值，要么就是至 i-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值，即：

dp[i] = max(dp[i-2]+nums[i], dp[i-1])

如果不能理解可以看下图：

（相当于小贼背了个背包，里边装了之前偷来的财物，每到达下一个房间门口，来选择是偷还是不偷。）

PNG

03、GO语言示例

分析完毕，我们根据第二种状态定义进行求解：

  1. func rob(nums []int) int {
  2.     if len(nums) < 1 {
  3.         return 0
  4.     }
  5.     if len(nums) == 1 {
  6.         return nums[0]
  7.     }
  8.     if len(nums) == 2 {
  9.         return max(nums[0],nums[1])
  10.     }
  11.     dp := make([]int, len(nums))
  12.     dp[0] = nums[0]
  13.     dp[1] = max(nums[0],nums[1])
  14.     for i := 2; i < len(nums); i++ {
  15.         dp[i] = max(dp[i-2]+nums[i],dp[i-1])
  16.     }
  17.     return dp[len(dp)-1]
  18. }
  20. func max(a,b int) int {
  21.     if a > b {
  22.         return a
  23.     }
  24.     return b
  25. }

运行结果：

PNG

同样，运行上面的代码，我们发现使用的内存过大。有没有什么办法可以压缩内存呢？我们很容易想到，在小贼偷盗的过程中，不可能转回头去到自己已经偷过的房间！（太蠢）小偷只需要每次将财物搬到下一个房间就行！


根据上面思路，优化后的代码如下：

  1. func rob(nums []int) int {
  2.     if len(nums) < 1 {
  3.         return 0
  4.     }
  5.     if len(nums) == 1 {
  6.         return nums[0]
  7.     }
  8.     if len(nums) == 2 {
  9.         return max(nums[0],nums[1])
  10.     }
  11.     nums[1] = max(nums[0],nums[1])
  12.     for i := 2; i < len(nums); i++ {
  13.         nums[i] = max(nums[i-2]+nums[i],nums[i-1])
  14.     }
  15.     return nums[len(nums)-1]
  16. }
  18. func max(a,b int) int {
  19.     if a > b {
  20.         return a
  21.     }
  22.     return b
  23. }

运行结果：

PNG