LeetCode刷题笔记-动态规划-day3

布满荆棘的人生 2023-10-01 17:30 36阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-动态规划-day3
 *   *  198. 打家劫舍
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  213. 打家劫舍 II
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  740. 删除并获得点数
     *   *  1.题目
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-动态规划-day3 ##

### 198. 打家劫舍 ###

#### 1.题目 ####

> 原题链接：[198. 打家劫舍][198.]

![image-20220207094442765][]

#### 2.解题思路 ####

我们可以用`f[i]`表示小偷走到第`i`个房间偷的总金额，可以分两种情况：

1.  小偷不选第`i`个房间的现金，那么`f[i]=f[i-1];`
2.  小偷选择偷第`i`个房间的现金，因为不能选择连续的房间，所以`f[i]=f[i-2]+nums[i];`

如图：![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-thAHvi6W-1644281720391)(https://gitee.com/llxpp/blog-image/raw/master/img/20220207100309.png)\]][img-thAHvi6W-1644281720391_https_gitee.com_llxpp_blog-image_raw_master_img_20220207100309.png]

> 图转载：https://www.acwing.com/solution/content/19504/

#### 3.代码 ####

class Solution {
        
    public:
        int rob(vector<int>& nums) {
        
            int n=nums.size();
            vector<int> f(n+1);
            if(n<2) return nums[0];
            f[0]=nums[0],f[1]=max(nums[0],nums[1]);
            for(int i=2;i<n;i++){
        
                f[i]=max(f[i-1],f[i-2]+nums[i]);
            }
            return f[n-1];
        }
    };

### 213. 打家劫舍 II ###

#### 1.题目 ####

> 原题链接：[213. 打家劫舍 II][213. _ II]

![image-20220207094507632][]

#### 2.解题思路 ####

从题意可知该题相比[198. 打家劫舍][198.]只是多了一个条件：**第一个房间和最后一个房间不能同时选**，因此我们可以枚举这两种情况：

1.  一定不选第一个，即求出`[2,n]`区间可以得到的最大价值
2.  一定不选最后一个，即求出`[1,n-1]`区间可以得到的最大价值

最后取两种情况的最大值即可。

#### 3.代码 ####

class Solution {
        
    public:
        int rob(vector<int>& nums) {
        
            int n=nums.size();
            vector<int> f(n+1);
            if(n<2) return nums[0];
            if(n==2) return max(nums[0],nums[1]);
            f[0]=nums[0],f[1]=max(nums[0],nums[1]);
            for(int i=2;i<n-1;i++){
        
                f[i]=max(f[i-1],f[i-2]+nums[i]);
            }
            int t1=f[n-2];
            f.clear();
            f[0]=0,f[1]=nums[1];
            for(int i=2;i<n;i++){
        
                f[i]=max(f[i-1],f[i-2]+nums[i]);
            }
            int t2=f[n-1];
            return max(t1,t2);
        }
    };

### 740. 删除并获得点数 ###

#### 1.题目 ####

> 原题链接：[740. 删除并获得点数][740.]

![image-20220207094532899][]

#### 2.解题思路 ####

仔细分析题目可知该题与[198. 打家劫舍][198.]相似，不同的是每个元素可能有多个。

因为题目要求了如果选择`num[i]`，就不能选择等于 `nums[i] - 1` 和 `nums[i] + 1` 的元素，等价于[198. 打家劫舍][198.]中我们不能选择连续的房间。

我们可以用`map`记录每个元素的个数，由题目给出的数字范围我们可以枚举1到10000的所有元素。用`f[i]`表示走到该点获取的最大点数，则：

`f[i]=max(f[i-1],f[i-2]+i*cnt[i]);`

#### 3.代码 ####

class Solution {
        
    public:
        int deleteAndEarn(vector<int>& a) {
        
            map<int,int> cnt;
            for(auto x:a) cnt[x]++;
            vector<int> f(10001);
            f[1]=1*cnt[1];
            for(int i=2;i<10001;i++){
        
                f[i]=max(f[i-1],f[i-2]+i*cnt[i]);
            }
            return f[10000];
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[198.]: https://leetcode-cn.com/problems/house-robber/
[image-20220207094442765]: https://img-blog.csdnimg.cn/img_convert/a65b1379cb025b304f2caa674b276b84.png
[img-thAHvi6W-1644281720391_https_gitee.com_llxpp_blog-image_raw_master_img_20220207100309.png]: https://img-blog.csdnimg.cn/aab43b76ee474c03b4de81a513b762b0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[213. _ II]: https://leetcode-cn.com/problems/house-robber-ii/
[image-20220207094507632]: https://img-blog.csdnimg.cn/img_convert/67e3476081861df6375e95cd0360208a.png
[740.]: https://leetcode-cn.com/problems/delete-and-earn/
[image-20220207094532899]: https://img-blog.csdnimg.cn/img_convert/2f7d8bb387de107f9513eaa6d2b820d5.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/b94fe38c3eea4dd49fa50d9b45251f61.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16