题目

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

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

示例 1:

1
2
3
4

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

示例 2:

1
2
3
4

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

题解

在有之前几道题的基础上，再做这道题就相对会容易一些，首先我们考虑这道题中有几个状态，2个。一个状态是房屋的编码，另一个状态是针对这个房屋是偷还是不偷，这样dp数组是dp[i][2]，其中i代表编号，而2代表偷与不偷这两种状态，dp数组中数据的含义是当前状态下我们所获得的最大金额。

下面来考虑状态转移方程，当我们到一个房屋前时，有两种状态，要么偷，要么不偷，这两种情况分别对应以下函数。

1
2
3
4

// 状态0代表不偷
dp[i][0] = max{ dp[i - 1][0], dp[i - 1][1] }
// 状态1代表偷
dp[i][1] = dp[i - 1][0] + nums[i]

如果某个房屋我们不偷，那么现在的收益就有两种情况，要么是前一个房屋也没偷的收益，要么是前一个偷了的收益，我们取这两者最大的收益作为当前房屋的收益。

如果现在这个房屋我们偷了，那显然收益就是前一个没偷的收益加上这个房屋的收益。

最终我们要的结果是到达最后一个房屋时，偷与不偷这两种状态的最大值，即max{ dp[N - 1][0], dp[N - 1][1]}。

实现代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int rob(vector<int>& nums) {
   int count = nums.size();
   if (count == 0)return 0;
   int (*dp)[2] = new int[count][2];
   dp[0][0] = 0;
   dp[0][1] = nums[0];
   for (int i = 1; i < count; i++) {
       dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
       dp[i][1] = dp[i - 1][0] + nums[i];
   }

   return max(dp[count - 1][0], dp[count - 1][1]);
}

从代码中可以看到，当前房屋的收益只与前一个房屋的收益有关，因此里面的dp数组可以优化，只需要4个变量保存即可，空间复杂度由O(N)降为O(1)。

看了官方的题解后，发现实现可以再简单一些的，自己考虑的这种实现中状态有2个，但可以优化成为1个，优化后的状态转移方程为：

1

dp[i] = max{dp[i - 1], dp[i - 2] + A[i]}

这里只有一个状态，即房屋编号，而偷与不偷这个状态隐藏在状态转移方程之中。dp数组的值为当前房屋下偷的的最大价值，那么我当前偷的最大价值是啥呢？就是前一个偷与当前房屋偷的这两个的最大值。

前一个偷，说明当前房屋不偷，前一个偷的最大价值就是dp[i - 1]；当前房屋偷，前一个房屋肯定不偷，那当前偷的价值就是 dp[i - 2] + A[i]，这里面是dp[i - 2]的价值，说明是按照前前房屋的价值计算的，把前一个房屋的价值略过，进而说明前一个房屋没有偷。

这样，最终的结果就是dp[N - 1]。这种实现代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int rob(vector<int>& nums) {
    int count = nums.size();
    if (count == 0)return 0;
    int *dp = new int[count];
    dp[0] = nums[0];
    for (int i = 1; i < count; i++) {        
        if (i == 1) {
            dp[1] = max(dp[0], nums[1]);
            continue;
        }

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

    return dp[count - 1];
}

这里的dp数组依旧可以优化，优化后只需要3个变量即可，这里不再赘述。