198.打家劫舍

发表于2022-02-24字数统计896阅读时长6分

LeetCode.198 打家劫舍

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

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

方法一

通过递归来搜索最大的抢劫路径，将问题划分为小的子问题。
每次搜索房屋其实只再两个房屋内做选择，设dp[i]为此次盗窃房屋，则下次盗窃房屋只能选择dp[i + 2]和dp[i + 3]两个房屋，假如已经知道盗窃这两个房屋后能获得的最大金额，则dp[i]最大值为max(dp[i + 2], dp[i + 3]) + nums[i]，就得到了前后量的关系。
对于第一次也有两种选择，即第一个房屋和第二个房屋，后选择和比较就和dp[i]的思路相同了。
对于最后一次即递归结束的条件，就是数组长度减去当前索引值小于3即说明没有选择就开始返回当前房屋金额并出栈，若等于3说明只能选择最后一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() > 1){
            return max(robOne(nums, 0), robOne(nums, 1));
        }else{
            return nums[0];
        }
    }
    int robOne(vector<int>& nums, int index) {
        if(nums.size() - index < 3){
            return nums[index];
        }else if(nums.size() - index == 3){
            return robOne(nums, index + 2) + nums[index];
        }else{
            return max(robOne(nums, index + 2), robOne(nums, index + 3)) + nums[index];
        }
    }
};

然鹅最后运行时间超出限制😥

方法二

刚才思想是自顶向下，这样就会造成多次从顶向下计算遍历重复的路径，所以可以尝试从低向上的动态规划。（其实上面方法更像是带反悔的贪心算法，我也不太清楚）
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])，如果是从隔壁抢劫过来的，则这一家就不能抢了，所以总量还是抢上一家的总量，如果是从间隔一个的房子抢过来，这家就还可以抢劫，所以总量就等于之前加上此房屋的。
想第一个方法的时候进入了一个误区，因为最开始想的是从顶向下的，总是想下一次可以抢劫后第二个或者后第三个房屋，但是对于从底向上来说，上一个房屋是前第二个或者前第三个都没有区别，因为

  • 如果前第三个被抢，也就是dp[i - 3]被抢了，则dp[i - 2] = dp[i - 3]，所以从前第三个房子或第二个房子过来抢，所带金额是一样的
  • 如果前第二个被抢，也就是dp[i - 2]被抢了，则dp[i - 2] >= dp[i - 3]，所以最大金额应该是从前第二个房子带过来的
    所以如果i房子被抢，从i - 2是绝对没错的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() < 2){
            return nums[0];
        }
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return max(dp[nums.size() - 1], dp[nums.size() - 2]);
    }
};