算法训练之动态规划（四）——简单多状态问题

---

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥

♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥

♥♥♥我们一起努力成为更好的自己~♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥

✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨

---

        在前面的博客中，我们已经练习了很多动态规划类型的题目，但是前面的动态规划仅仅是单独状态的，今天这一篇博客我们一起来探索一下简单多状态动态规划类型的题目~准备好了吗~我们发车去探索奥秘啦~🚗🚗🚗🚗🚗🚗

目录

按摩师（打家劫舍）

打家劫舍Ⅱ

删除并获得点数

---

按摩师（打家劫舍）

按摩师（打家劫舍）

        前面已经提到了这是一种简单多状态的dp问题，那么这个多状态体现在哪里呢？题目要求不可以接受相邻的预约，那么就说明每一个位置的状态可能是选择的，也可能是没有选择的~这就有两个状态了，那么有两个状态我们应该怎么表示呢？我们可以创建两个dp表，接下来我们结合前面的思想来分析一下这道多状态问题~

分析：

1、状态表示

题目要求：不可以接受相邻的预约，那么每一个预约有选择和不选择这两种状态~我们创建两个dp表来进行表示

        结合这里的题目要求+经验：

        dp1中的dp1[i]表示为到达该位置并且选择该位置预约的最长预约时间~

        dp2中的dp2[i]表示为到达该位置并且不选择该位置预约的最长预约时间~

2、状态转移方程

       我们以离【i】位置最近的状态分析状态转移方程，处理两个dp表

1、dp1【i】选择【i】位置，那么说明前面的位置是一定不可以选择的，那么dp1[i]=dp2[i-1]+nums[i]

2、dp2【i】不选择【i】位置，那么说明前面的位置可以选择、也可以不选择，取两者的最大值~那么dp2[i]=max(dp1[i-1],dp2[i-1]

3、初始化

        我们可以看到，状态转移方程里面有i-1当i=0的时候显然会出现越界的情况，所以我们需要进行初始化

        结合前面如果不想初始化太麻烦，我们可以多申请一些空间，但是事实上这个题目初始化比较简单，直接初始化dp1[0],dp2[0]就可以了，所以我们直接进行初始化~

        dp1[0]就是选择0位置预约， dp2[0]就是不选择0位置预约，那么我们初始化结果就是

                dp1[0]=nums[0],dp2[0]=0

4、填表顺序

        我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前往后

5、返回结果

      这里返回结果是最后一个位置，最后一个位置有两种情况，一种是选择最后一个位置，一种是不选择最后一个位置，返回两种情况最大值就可以了，即返回max(dp1[n-1],dp2[n-1])

注意点：这里需要处理一下元素个数为0的边界情况

有了前面的分析，代码实现就比较简单了~

代码实现：

class Solution 
{
public:int massage(vector<int>& nums) {//1、创建两个dp表int n=nums.size();//处理边界情况if(n==0) return 0;vector<int> dp1(n);vector<int> dp2(n);//2、初始化dp1[0]=nums[0];dp2[0]=0;//3、填表for(int i=1;i<n;i++){dp1[i]=dp2[i-1]+nums[i];dp2[i]=max(dp1[i-1],dp2[i-1]);}//4、返回结果return max(dp1[n-1],dp2[n-1]);}
};

顺利通过~

打家劫舍Ⅱ

打家劫舍Ⅱ

        这个题目和上一道题目是十分类似的，不过题目多了头尾不能同时选择的条件~那么我们是不是就可以根据【0】位置是否选择来进行区分：

        1、选择【0】位置，显然【1】位置和【n-1】位置都不能进行选择了，但是在【2】~【n-2】这个区间内，我们不就可以随便选择了吗~也就可以使用前面我们打家劫舍的思路了~

        2、不选择【0】位置，显然【1】位置和【n-1】位置都能进行选择，那么在【1】~【n-1】这个区间内，我们就可以随便选择~也就可以使用前面我们打家劫舍的思路了~

这个题目与前面的分析高度类似，就不进行重复分析了~

优化：我们可以把打家劫舍的代码优化成一个函数进行调用~

我们来看看代码实现：

class Solution 
{
public://打家劫舍一int rob1(vector<int>& nums,int left,int right){if(left>right) return 0;//处理不合法情况//也就处理了边界情况//1、创建两个dp表//vector<int> dp1(right-left+1);//vector<int> dp2(right-left+1);//优化：减少映射关系处理，直接申请n个大小空间int n=nums.size();vector<int> dp1(n);vector<int> dp2(n);//2、初始化dp1[left]=nums[left];dp2[left]=0;//3、填表//注意填表范围和顺序for(int i=left+1;i<=right;i++){dp1[i]=dp2[i-1]+nums[i];dp2[i]=max(dp1[i-1],dp2[i-1]);}//4、返回结果//注意返回位置return max(dp1[right],dp2[right]);}int rob(vector<int>& nums) {int n=nums.size();return max(nums[0]+rob1(nums,2,n-2),0+rob1(nums,1,n-1));}
};

顺利通过~

删除并获得点数

删除并获得点数

        这个题目看起来有点难，看题目要求相邻的两个数是不可以同时存在的，这个不就与我们的打家劫舍类似嘛？那么我们怎么将这个题目与打家劫舍联系起来呢？这里是数不能相邻，那么我们就可以把每一个数的累加和保存到一个数组中，利用数组下标就可以找到他~同时数组下标是相邻的，再对这个数组用一次打家劫舍的思想就可以~

        这个题目与前面的动态规划分析高度类似，就不进行重复分析了~

代码实现：

class Solution
{
public:int deleteAndEarn(vector<int>& nums){//预处理//问题转化int n = nums.size();int m = 0;//不要用max命名，容易与算法库max混淆for (auto e : nums){if (e > m)m = e;}vector<int> arr(m + 1);//根据最大数据开辟空间for (auto e : nums){arr[e] += e;//统计数据和}//动态规划//1、创建两个dp表vector<int> dp1(m + 1);vector<int> dp2(m + 1);//2、初始化dp1[0] = arr[0], dp2[0] = 0;//3、填表for (int i = 1; i < m + 1; i++){dp1[i] = dp2[i - 1] + arr[i];dp2[i] = max(dp1[i - 1], dp2[i - 1]);}//4、返回结果return max(dp1[m], dp2[m]);}
};

        顺利通过~

        事实上，我们这里还可以进一步优化，题目给出了数据范围，那我直接创建一个跟最大数据一样的数组就好~

class Solution
{
public://优化版int deleteAndEarn(vector<int>& nums){//1、预处理const int N = 10001;//更加方便写vector<int> arr(N);for (auto e : nums)arr[e] += e;//2、动态规划vector<int> dp1(N);vector<int> dp2(N);dp1[0] = arr[0];dp2[0] = 0;for (int i = 1; i < N; i++){dp1[i] = dp2[i - 1] + arr[i];dp2[i] = max(dp1[i - 1], dp2[i - 1]);}return max(dp1[N - 1], dp2[N - 1]);}
};

        顺利通过~

        当然，还可以进一步优化，如果只有几个数，动态表开辟那么大的空间，还是有点浪费的，我们可以把前面两个方法结合一下~

        最终版：

class Solution
{
public://最终版int deleteAndEarn(vector<int>& nums){//1、预处理const int N = 10001;//更加方便写int m = 0;vector<int> arr(N);for (auto e : nums){arr[e] += e;m = max(m, e);//统计数据和的同时找数组最大值}//2、动态规划vector<int> dp1(m + 1);vector<int> dp2(m + 1);dp1[0] = arr[0];dp2[0] = 0;for (int i = 1; i < m + 1; i++){dp1[i] = dp2[i - 1] + arr[i];dp2[i] = max(dp1[i - 1], dp2[i - 1]);}return max(dp1[m], dp2[m]);}
};

顺利通过~

---

♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

✨✨✨✨✨✨个人主页✨✨✨✨✨✨

---