代码随想录Day50-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录Day50。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

昨天因为准备面试所以咕咕了一天。今天继续学习动规算法，尽管背包问题已经结束但其中的各类思想仍需要进一步理解。

198.打家劫舍

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

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

示例 1：

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

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

思路：

1.有了前面一段时间的学习，本题还是能比较轻易看出来要使用动规的，因为到当前房屋能偷到的最大金额与前面偷到的最大金额是有关联并且是由其推导出来的。但不要因为做了一段时间的背包问题了就给固化思路想背包上面去了

2.首先想dp数组含义，dp[i]表示包括i及其之前的房屋所能偷到的最大金额。

3.然后想递推公式，对于当前房屋有两种选择：偷或者不偷。如果偷，那么一定是将到i - 2的房屋能偷到的最大金额与当前房屋金额相加；如果不偷，那么我们考虑i-1的房屋能偷到的最大金额。因此递推公式为dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。

4.然后想初始化，本题的初始化相比起之前思路上好想一点，但初始化的数值不再是单纯的0或者1之类的。对于dp[0]，显然是一定要将nums[0]赋值给它的，第一间屋子如果都不偷那还求什么最大值？

然后对于dp[1]，因为不能偷相邻的房子，因此我们得看是偷下标为0的屋子还是下标为1的屋子，对这两个的金额取一个最大值进行赋值

5.然后想遍历顺序，本题显然是从前往后进行遍历，因为最后的最大金额需要由前面的最大金额推导出来。（注意不是背包问题了！！！不要固化进一旦是动规就想先物品还是背包之类的！！！）

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(), 0);

        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 dp[nums.size() - 1];
    }
};

启发：

1.本题在有了前面的学习基础之后还是比较好想的一道题，但因为前面背包问题作为一大重点学习了一段较长的时间，刚脱离背包问题后思路还是有一点固化在了里面，需要尽快调整。

213.打家劫舍||

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

思路：

1.本题在上一题基础之上稍微变化了一点就容易混淆思路了。既然出现了环，那么到底起始位置选在哪里就成了一个纠结的问题......在一顿纠结后想起前一道题，如果能够将环重新转化为线性结构就能够很轻松的解决了，而阻碍转化为线性结构的点无非就是第一个房子和最后一个房子，那么将这两者拆开讨论不就可以转化为线性结构了吗？那么我们就分两次求最大金额，一次只考虑第一个房子，一次只考虑最后一个房子，最后再对这两者取一个最大值就可以了。确定以上思路后，动规的逐步实现实际上就与上一道题完全一致了。

class Solution {
public:
    int robRange(vector<int>& nums, int start, int end){
        if(start == end) return nums[start];
        vector<int> dp(nums.size(), 0);

        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);

        for(int i = start + 2; i <= end; i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[end];
    }

    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];

        int result1 = robRange(nums, 1, nums.size() - 1);//不考虑第一个屋子
        int result2 = robRange(nums, 0 , nums.size() - 2);//不考虑最后一个屋子

        return max(result1,result2);
    }
};

启发：

1.本题实际上考察的就是一个如何将环重新转化为线性结构的思路，只要想清楚本题的环之所以为环实际上就是首尾相连，那么将首和尾拆开各自划分为一种情况单独考虑就能解决问题了。文章来源地址https://www.toymoban.com/news/detail-413398.html

到了这里，关于代码随想录Day50的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！