【力扣刷题 | 第十六题】

阳光穿透心脏的1/2处 2024-03-16 23:47 68阅读 0赞

![e26a15d4a69945aeb530891fc8a936c1.jpeg][]

**目录**

前言：

198. 打家劫舍 - 力扣（LeetCode）

213. 打家劫舍 II - 力扣（LeetCode）

总结：

--------------------

## 前言： ##

我们今天继续刷动态规划的题，希望大家可以和我一起坚持下去。

## [198. 打家劫舍 - 力扣（LeetCode）][198. _ - _LeetCode] ##

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

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

![50b4c87f07174226a8852d9a07257ee8.png][]

解题思路：我们要先快速确定出这道题的解题方向，我们读题后发现：当前房间偷不偷，取决于它前一个房间有没有被偷，因此可以确定出房间之间是存在这样一个递推关系的，因此我们确定了动态规划的思路，既然是动态规划，我们就严格按照动态规划五步走：

**1.确定dp数组的含义以及下标的含义**：dp\[i\]表示包含这个房间他所能偷盗的最大金币的总和。

**2.递推公式：**我们用图片举例，假设此时我们要判断到最后一个房间的时候最大的金币数

> 其实就两个状态我们分类讨论：
> 
> **1.偷最后一个房间：**![b3589a524b4846b1830d750dd1bdef25.png][]
> 
> 既然**5房间决定要偷了，那么4房间一定不偷**，那么此时能够获得到的最大金币**dp\[5\]其实就等于nums\[5\]+dp\[3\]。**我们要理解正确理解dp数组的含义，才可以理解这个公式。
> 
> 我们这里的下标只是为了方便理解，实际上我们在构建的时候，dp数组是从0开始的，也就是说dp\[0\]就是第一次房间能够偷到的最大金币数。
> 
> **2.不偷最后一个房间：**  
> ![5bde7015b37046dfa28b4709cbb8f98d.png][]
> 
> 既然5房间不偷，那么此时能够得到的最大金币 **dp\[5 \]= dp\[4\],**此时我们的问题就又回到了对dp\[4\]进行讨论，也就是对4号房间再次进行偷与不偷的讨论。
> 
> 经过这个讲解，相信大家其实对打家劫舍问题的递推思路已经清晰：我们每一次比较这个这个房间偷与不偷所得到的金币数量，选择较大的作为dp数组的元素，这样不断递推，最后返回最后一个房间对应的dp数组的元素。
> 
> 公式为： **dp\[i\]=max(nums\[i\]+dp\[i-2\],dp\[i-1\]);**

**3.dp数组的初始化：**我们根据递推公式就可以知道只需要初始化dp\[0\]与dp\[1\]的值就好了。其实二者的初始化很好理解：  
dp\[0\]:从头开始包含第一个房间的最大金币数，那么当前只有一个房间，要想得到最大金币数就必须偷这个房间，那就是dp\[0\]=nums\[0\]。

dp\[1\]:从头开始到第二间房间的最大金币数，因为我们不能偷相邻的两个房间，那么想要得到最大的金币数，就只能偷1或者偷2，选择最大的偷。那么就是dp\[1\]=max(dp\[0\],dp\[1\])。

**4.遍历顺序：**根据公式可得是从前往后推，遍历顺序自然也是从前往后。

经过我们详细的分析，代码的框架其实就已经搭建起来了，我们要做的只剩下补全这个框架。

class Solution {
    public:
        int rob(vector<int>& nums) {
            if(nums.size()==1)
            {
                return nums[0];
            }
            else if(nums.size()==2)
            {
                return max(nums[0],nums[1]);
            }
           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(nums[i]+dp[i-2],dp[i-1]);
           }       
           return dp[nums.size()-1];
        }
    };

## [213. 打家劫舍 II - 力扣（LeetCode）][213. _ II - _LeetCode] ##

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

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

![c7642ef0a1ee4639b520d1225fa1c5ff.png][]

其实这道题就是把改变了房间结构，让首尾相连，房间结构从线性变为了环形。

![58eeccb3fc474c489d6ee113610ce7a8.png][]其实就是分类讨论：

**因为此时首尾元素相连，因此我们在选择的时候只有两种可能：**

**1.一定不偷尾。**

**2.一定不偷首。**

![e6abe7995c86403b93e4c1b73b5acb8d.png][]

在明确逻辑之后，代码就非常明确了：

class Solution {
    public:
        int rob(vector<int>& nums) {
    
            if (nums.size() == 0) 
            {
                return 0;
            }
            if (nums.size() == 1)
            { 
                return nums[0];
            }
            int result1 = getmax(nums, 0, nums.size() - 2); //不对首进行考虑
            int result2 = getmax(nums, 1, nums.size() - 1); //不对尾进行考虑
            return max(result1, result2);
        }
        
        int getmax(vector<int>& nums, int start, int end) {
            if (end == start) return nums[start];
            vector<int> dp(nums.size());
            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 - 2] + nums[i], dp[i - 1]);
            }
            return dp[end];
        }
    };

我们对改动做一下讲解：该函数的目的是计算在\[start,end\]范围内选择数字进行相加得到的最大和，其中每个数字只能选择一次。函数的实现过程如下：

1. 如果开始位置和结束位置相等，则直接返回数组下标为start的数字作为最大和。  
2. 首先，我们定义一个大小与原始数组相同的dp数组，dp\[i\]表示在范围\[0,i\]内选择数字得到的最大和。  
3. 然后，我们初始化dp\[0\]为nums\[0\]，dp\[1\]为max(nums\[0\], nums\[1\])，因为在第一和第二个位置的数字中选择最大的那个能够确保我们得到最大和。  
4. 接下来，我们从第三个位置（即start+2）开始，循环遍历整个数组。在每个位置i处，我们有两种选择：

*  选择当前位置i的数字，这时最大和为dp\[i-2\]+nums\[i\]；
 *  不选择当前位置i的数字，这时最大和为dp\[i-1\]。

5. 将两种选择的结果取max，更新dp\[i\]。  
6. 最后，返回dp\[end\]作为\[start,end\]范围内选择数字相加得到的最大和。

需要注意的是，该算法的时间复杂度为O(N)，其中N为数组的长度。

## 总结： ##

打家劫舍类型题目里面给我们提供的这个算法思路真的很精彩，不愧是动态规划的经典例题。

如果我的内容对你有帮助，请**点赞，评论，收藏**。创作不易，大家的支持就是我坚持下去的动力！

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[e26a15d4a69945aeb530891fc8a936c1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/24901ac809d843d0891a80d893684b68.png
[198. _ - _LeetCode]: https://leetcode.cn/problems/house-robber/
[50b4c87f07174226a8852d9a07257ee8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1f72db8b9be44a4eb8bbfa66ab772c91.png
[b3589a524b4846b1830d750dd1bdef25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f1cb601da4db44f896e501e622331bde.png
[5bde7015b37046dfa28b4709cbb8f98d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a70c7869804c437f8e6193e47faad09f.png
[213. _ II - _LeetCode]: https://leetcode.cn/problems/house-robber-ii/
[c7642ef0a1ee4639b520d1225fa1c5ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7c57d035662646679b8966c7fc21e8db.png
[58eeccb3fc474c489d6ee113610ce7a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fa6c4ae6129c4bb29811cf4d5f578c71.png
[e6abe7995c86403b93e4c1b73b5acb8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d45e0dc6a4c44f279b89e344777eac15.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f3f6d153fc4b4e61928e6fcd066f2495.png