198. 打家劫舍

198. 打家劫舍#

题目链接

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

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

1
cost = [1,2,3,4,5,6,7,8]

因为有报警系统的原因，所以我们不能连着偷两栋，比如说我们偷了1，那么我们就不能偷2了

这时候我们的第一个想法就出来了，既然我们不能连着偷，那么隔一个偷一个大概就是最好的方案了吧，我们可以从第一栋开始偷，也可以从第二栋开始偷，如果我们从第三栋开始的话，那就和第一栋开始偷一样了，所以摆在我们面前的选择只有两个，偷奇数栋或者偷偶数栋

1
class Solution {
2
public:
3
    int rob(vector<int>& nums) {
4
        int odd=0,even=0;
5
        //定义两个计数器
6
        for(int i = 0;i < size(nums) ; i += 2){
7
            odd += nums[i];
8
            if(i + 1 < size(nums)) even += nums[i + 1];
9
            //如果存在偶数次的话就加上
10
        }
11
        return max(odd , even);
12
        //返回其中最大的
13
    }
14
};

写完了直接提交，然后发现不行（；´д｀）ゞ

1
cost = [2,1,1,2]

我们倒在了这个样例上，在这个例子上，偷第一家和最后一家才是最优的结果，他们的奇偶性不同，所以我们的程序不会考虑这种可能

这就麻烦了，我们应该如何处理这样的例子呢

对于这样要我们去规划路径的题，我们知道直接找出整体最优解是不太可能的，那么我们就来看看局部最优解怎么算

1
cost = [1,2,3]

我们回到最初的例子上面，但我们先只看前3项，我们经过前三户人家的时候我们最多能偷多少钱呢，我们有两个可能

1. 偷第1户和第3户 总钱数 = 1 + 3 = 4
2. 只偷第2户 总钱数 = 2

所以对于前3项来说，总钱数最多为4，让我们再来看看前4项

1
cost = [1,2,3,4]

对于前4项，也有两种可能

1. 偷第2户和第4户 总钱数 = 2 + 4 = 6
2. 偷第1户和第3户 总钱数 = 1 + 3 = 4

这时候我们好像隐隐感觉到了一丝规律（没感觉到也没事）

再看前5项

1
cost=[1,2,3,4,5]

两种可能

1. 偷1、3、5户的 总钱数 =1 + 3 + 5 =9
2. 偷2、4户的 总钱数 = 2 + 4 = 6

我们看到这里的“1 + 3 + 5”中的“1 + 3”我们之前算过啊，以及“2 + 4”我们也算过啊

然后我们就能总结出规律，假设我们在前i项，第一种可能总是为：第i间房本身的钱 + 前i-2间房最多能偷到的钱。第二种可能总是为：前i-1间房最多能偷到的钱

写成代码就是

1
M[i] = max(
2
    cost[i] + M[i-2],
3
    M[i-1]
4
    )
5
//M[i]代表第i间房最多能偷到的钱
6
//max代表在两个中选一个最大的

有了这个公示后就可以开始推导了，前1间由于没有前面的房子，所以永远是其本身的钱，即M[0] = B[0]，第2间房有了前面的房子的结果，因为没有M[i-2]所以把M[i-2]视为0，接着套公式，第三间房有了前两间也可以直接套，后面的房子同理，这样我们就能算出前n间房最多能偷多少了

下为示例代码

1
class Solution {
2
public:
3
    int rob(vector<int>& nums) {
4
        int n1 = nums[0],n2 = 0;
5
    //这里n1表示M[i-1],n2表示M[i-2]
6
    //值得注意的是，观察公式发现，除了cost以外，我们只需要额外存储两个值，分别是M[i-1]，M[i-2]
7
        for(int i = 1;i < size(nums);i++){
8
      //但是实际上，我们必须要多写一个变量才能实现两个值的更新
9
            int curl=max(n1,n2+nums[i]);
10
      //curl用来存储M[i]的值
11
            n2 = n1;
12
            n1 = curl;
13
      //这里将n2变成M[i-1],n1变成[i]，之后执行i++，这些值整体前移
14
        }
15
        return n1;
16
    }
17
};