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

---

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

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

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

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

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

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

---

        这一篇博客我们继续来看看动态规划系列里面的简单多状态问题，准备好了吗~我们发车去探索奥秘啦~🚗🚗🚗🚗🚗🚗

目录

粉刷房子

买卖股票的最佳时机（含冷冻期）

---

粉刷房子

粉刷房子

        可以看到题目要求给房子上颜色，并且相邻的房子颜色不能相同~这显然是是一个多状态的问题，接下来我们来一步步分析一下~

分析：

1、状态表示

        题目要求：相邻的房子颜色不能相同，每一个房子有三种颜色可以选择~我们创建三个dp表来进行表示，事实上，题目给出的二维数组，行号就是房子号数，列号是涂某一种颜色的花费，我们也可以用这样一个二维数组来形成我们的dp表~每一个房子都有三种不同的情况~

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

        dp表中的dp1[i][0]表示为到达该位置并且选择该位置选择涂红色的最小花费~

        dp表中的dp1[i][1]表示为到达该位置并且选择该位置选择涂蓝色的最小花费~

        dp表中的dp1[i][2]表示为到达该位置并且选择该位置选择涂绿色的最小花费~

2、状态转移方程

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

1、

        dp【i】【0】选择【i】位置涂红色，那么说明前面的位置是一定不可以涂蓝色和绿色的，取两者最小值再加上当前位置涂红色的花费，那么

                dp[i][0]=min(dp[i-1][1],dp[i-1][2])+nums[i][0]

2、

        dp【i】【1】选择【i】位置涂蓝色，那么说明前面的位置是一定不可以涂红色和绿色的，取两者最小值再加上当前位置涂蓝色的花费，那么

                dp[i][1]=min(dp[i-1][0],dp[i-1][2])+nums[i][1]

3、

        dp【i】【2】选择【i】位置涂绿色，那么说明前面的位置是一定不可以涂蓝色和红色的，取两者最小值再加上当前位置涂绿色的花费，那么

                dp[i][2]=min(dp[i-1][0],dp[i-1][1])+nums[i][2]

3、初始化

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

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

        dp[0][0]就是选择0位置涂红色花费nums[0][0]， dp[0][1]就是选择0位置涂蓝色花费nums[0][1]， dp[0][2]就是选择0位置涂绿色花费nums[0][2]那么我们初始化结果就是

                dp[0][0]=nums[0][0] , dp[0][1]=nums[0][1] , dp[0][2]=nums[0][2]

4、填表顺序

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

5、返回结果

      这里返回结果是到最后一个房子的最小花费，最后一个房子有三种情况，一种是选择涂红色，一种是选择涂蓝色，还有一种是选择涂绿色，返回三种情况最小值就可以了，即返回min(min(dp[m-1][0],dp[m-1][1]),dp[m-1][2])

注意点：结合题目给出的范围，这里不需要处理边界情况~

代码实现：

class Solution
{
public:int minCost(vector<vector<int>>& costs){//1、创建dp表int m = costs.size();//房子号int n = costs[0].size();//颜色vector<vector<int>> dp(m, vector<int>(n));//2、初始化dp[0][0] = costs[0][0];dp[0][1] = costs[0][1];dp[0][2] = costs[0][2];//3、填表for (int i = 1; i < m; i++){dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];}//4、返回结果return min(min(dp[m - 1][0], dp[m - 1][1]), dp[m - 1][2]);}
};

顺利通过~

我们也可以采用有趣提到的增加虚拟节点的方法，这里相当于多增加一个空房子，有下面两个注意点：

1、虚拟节点值是多少？

        虚拟节点会影响到第一个房子的最小花费，事实上，到第一个房子的最小花费也就是第一个房子的花费，不想让虚拟节点影响，就把虚拟节点值设置为0~

2、注意下标映射关系

        相当于增加了一个房子，注意与原来的数组的下标映射~

代码实现：

class Solution
{
public:int minCost(vector<vector<int>>& costs){//使用虚拟节点//1、创建dp表int m = costs.size();int n = costs[0].size();//也可以直接写为已知的3vector<vector<int>> dp(m + 1, vector<int>(n));//2、初始化虚拟节点dp[0][0] = 0;dp[0][1] = 0;dp[0][2] = 0;//3、填表for (int i = 1; i <= m; i++){//注意下标映射关系dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];}//4、返回结果return min(min(dp[m][0], dp[m][1]), dp[m][2]);}
};

顺利通过~不难发现，代码量其实是差不多的，大家选择自己喜欢的方式就好~

买卖股票的最佳时机（含冷冻期）

买卖股票的最佳时机（含冷冻期）

        这个题目显然是一个多状态问题，那么我们首先得分析它有哪几个状态：

1、买入状态（也就是手上有股票的状态，可以进行卖出）

2、冷冻期状态（不可以进行买入）

3、可以交易的状态（可以进行买入）

接下来画图分析这几个状态之间的关系（也就是讨论状态相互之间是否可达以及是否可以自己到自己）

知道了这三个状态之间的关系，我们就可以利用动态规划的思想进行分析：

1、状态表示

        题目要求：既然有三个状态，那么我们就需要创建三个dp表表示不同位置可能的状态~

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

        dp1表中的dp1[i]表示为到达该位置进行操作后处于买入状态的最大利润~

        dp2表中的dp2[i]表示为到达该位置进行操作后处于可交易状态的最大利润~

        dp3表中的dp3[i]表示为到达该位置进行操作后处于冷冻期状态的最大利润~

        注意是在该位置进行操作后处于什么状态，而不是到达该位置是什么状态，这样会比较麻烦~

2、状态转移方程

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

1、

       怎么样会处于买入状态呢？结合前面的画图分析可能是前一天可交易状态下，在今天买入股票变成买入状态；也可能是前一天买入状态下，今天什么都不干依然是买入状态，取两种情况的较大值~

        dp1表状态转移方程：

        dp1[i]=max(dp1[i-1],dp2[i-1]-prices[i]);

2、

        怎么样会处于可交易状态呢？结合前面的画图分析可能是前一天冷冻期状态，今天就是可交易的状态；也可能是前一天可交易状态下，今天什么都不干依然是可交易状态，取两种情况的较大值~

        dp2表状态转移方程：

        dp2[i]=max(dp2[i-1],dp3[i-1]);

3、

       怎么样会处于冷冻期状态呢？结合前面的画图分析可能是前一天处于买入状态，在今天进行卖出也就处于冷冻期状态了~没有其他情况

        dp3表状态转移方程：

        dp3[i]=dp1[i-1]+prices[i];

3、初始化

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

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

        dp1[0]就是第一天操作后处于买入状态，那么利润为-prices[0];

        dp2[0]就是第一天操作后处于可交易状态，那就是什么都不干，那么利润为0;

        dp3[0]就是第一天操作后处于冷冻期状态，这是不可能的，那么利润为0;

        那么我们初始化结果就是

                dp1[0]=-prices[0] , dp2[0]=0 , dp3[0]=0

4、填表顺序

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

5、返回结果

      这里返回结果是到最后一天的最大利润，最后一天有三种情况，返回三种情况最大值就可以了，即返回return max(max(dp1[n-1],dp2[n-1]),dp3[n-1]);

        当然，最后一天是不可能还处于买入状态的，这样就亏了，也就可以返回return max(dp2[n-1],dp3[n-1]);

注意点：结合题目给出的范围，这里不需要处理边界情况~

代码实现：

class Solution 
{
public:int maxProfit(vector<int>& prices) {//1、创建dp表int n=prices.size();vector<int> dp1(n);//买入状态vector<int> dp2(n);//可以交易状态vector<int> dp3(n);//冷冻期状态//2、初始化dp1[0]=-prices[0];dp2[0]=0;dp3[0]=0;//3、填表for(int i=1;i<n;i++){dp1[i]=max(dp1[i-1],dp2[i-1]-prices[i]);dp2[i]=max(dp2[i-1],dp3[i-1]);dp3[i]=dp1[i-1]+prices[i];}//4、返回结果//return max(max(dp1[n-1],dp2[n-1]),dp3[n-1]);return max(dp2[n-1],dp3[n-1]);}
};

顺利通过~

除了这种创建dp表的方式，我们也可以像前面那样创建二维数组（n*3）来实现三个dp表~

我们重新来进行分析一下：

1、状态表示

        题目要求：既然有三个状态，那么我们就需要创建三个dp表表示不同位置可能的状态~这里创建一个n*3的二维数组来表示~

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

        dp表中的dp[i][0]表示为到达该位置进行操作后处于买入状态的最大利润~

        dp表中的dp[i][1]表示为到达该位置进行操作后处于可交易状态的最大利润~

        dp表中的dp[i][2]表示为到达该位置进行操作后处于冷冻期状态的最大利润~

2、状态转移方程

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

1、

       怎么样会处于买入状态呢？结合前面的画图分析可能是前一天可交易状态下，在今天买入股票变成买入状态；也可能是前一天买入状态下，今天什么都不干依然是买入状态，取两种情况的较大值~

        dp表状态转移方程：

        dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);

2、

        怎么样会处于可交易状态呢？结合前面的画图分析可能是前一天冷冻期状态，今天就是可交易的状态；也可能是前一天可交易状态下，今天什么都不干依然是可交易状态，取两种情况的较大值~

        dp表状态转移方程：

        dp[i][1]=max(dp[i-1][1],dp[i-1][2]);

3、

       怎么样会处于冷冻期状态呢？结合前面的画图分析可能是前一天处于买入状态，在今天进行卖出也就处于冷冻期状态了~没有其他情况

        dp表状态转移方程：

        dp[i][2]=dp[i-1][0]+prices[i];

3、初始化

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

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

        dp[0][0]就是第一天操作后处于买入状态，那么利润为-prices[0];

        dp[0][1]就是第一天操作后处于可交易状态，那就是什么都不干，那么利润为0;

        dp[0][2]就是第一天操作后处于冷冻期状态，这是不可能的，那么利润为0;

        那么我们初始化结果就是

               

        dp[0][0]=-prices[0];//买入状态

        dp[0][1]=0;//可交易状态

        dp[0][2]=0;//冷冻期状态

4、填表顺序

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

5、返回结果

      这里返回结果是到最后一天的最大利润，最后一天有三种情况，返回三种情况最大值就可以了，即返回return max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);

        当然，最后一天是不可能还处于买入状态的，这样就亏了，也就可以返回return max(dp[n-1][1],dp[n-1][2]);

代码实现：（逻辑都是差不多的，只不过实现上有区别）

class Solution
{
public:int maxProfit(vector<int>& prices){//1、创建二维数组dp表int n = prices.size();vector<vector<int>> dp(n, vector<int>(3, 0));//2、初始化dp[0][0] = -prices[0];//买入状态dp[0][1] = 0;//可交易状态dp[0][2] = 0;//冷冻期状态//3、填表for (int i = 1; i < n; i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);dp[i][2] = dp[i - 1][0] + prices[i];}//4、返回结果return max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);//return max(dp[n-1][1],dp[n-1][2]);}
};

顺利通过~

---

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

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

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

---