【 C/C++ 算法】入门动态规划 ----- 简单多状态 dp 问题》打家劫舍 和 股票买卖问题
每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
绪论：
————————
本章是dp的第三章，从第一章的简单理解dp的核心框架和写法&一维dp，再到第二章的路径问题&二维dp，到本章的多状态dp问题，本章将结合前面的所有基础引入多状态这个问题，并将由浅到深的从简单的打家劫舍两状态的dp到最后股票问题的四状态dp进行以练代学的方式学习，并且过程中会不断总结（具体见目录）。友情提示若没看过前面篇章的动规小白一定要先看看前面两章并简单练习下再往后看（一维dp - 路径dp），后续还将持续更新，敬请期待~
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。
打家劫舍
常见的思考是否使用打家劫舍问题时，遇见相邻问题不能选择此时就能思考是不是要使用打家劫舍
打家劫舍，常使用个dp表进行存储情况
- f [ i ]：选择 i 位置时的最大价值
- g [ i ]：不选择 i 位置时的最大价值
具体训练：
按摩师
题目：
分析题目并提出，解决方法：
不能连续的选择，求找到最长的预约时长
- 状态表示：（题意 + 经验 ——》 从右往左）
dp[ i ]：选择到 i 位置的时候，此时的最长预约时长- 此处将dp分为两种状态：（因为这题题意是对于每个状态是又有两种不同的状态的所以进行划分，具体如下）
f[ i ]：选择时的最长预约
- 状态转移方程
- 那么就可以分析两种情况的状态转移方程：
- 选择i位置时（也就是f[ i ]），那么就是要加上 i - 1 不选的最大值
- 那么就可以分析两种情况的状态转移方程：
- 初始化：（回顾初始化的目的：保证保证填表不越界）
- 因为要使用
f[i-1]&g[i-1]，所以初始化 f[0] & g[0] - 具体初始化：
- f[0] = num[0]（也就是直接填入第一个位置的时长即可）
- g[0] = 0（若该点不选那么就为0）
- 因为要使用
- 填表顺序：从左往右，两表一起填（因为他们是互相需要的）
- 返回值 max(f[n-1],g[n-1])，最后一个位置选/不选的最大值
不选择i位置时（g[ i ]），那么值就是前 i - 1 位置的选或者不选的最大值（具体如下图）
g[ i ]：不选时的最长时长
题解核心逻辑：
其中主要逻辑就是上述分析
细节对于直接使用下标访问的情况，要处理一下边界情况，如可能n==0时，开辟的空间就为0
那么直接使用f[ 0 ] 就有可能非法访问
//不使用虚拟节点classSolution{public:intmassage(vector<int>& nums){//1. dp 表int n = nums.size(); vector<int>f(n,0);//选择i位置 vector<int>g(n,0);//不选择i位置if(n ==0)return0;//对于这种使用到下标的位置，一定要处理好边界情况，可能n为0呢 f[0]= nums[0];for(int i =1;i < n;i++){ f[i]= g[i-1]+ nums[i];// g[i]=max(g[i-1],f[i-1]);//从 选 i - 1 位置 和不选 i - 1位置中选较大的}int ret =max(g[n-1],f[n-1]);return ret;}};//使用虚拟节点：（方便不用初始化）classSolution{public:intmassage(vector<int>& nums){//f[i]：选择第 i 天，最大的分钟数,f[i] = g[i-1] + arr[i]（选择第i天，就代表不选择第i-1天 + 当前的分钟数）//g[i]：不选择第 i 天，最大的分钟数，g[i] = max(f[i-1],g[i-1])(不选择第i天就值为选择第i-1天 / 不选择第i-1天的最大值)int n = nums.size(); vector<int>f(n+1);//选择第i天 vector<int>g(n+1);//不选择第i天for(int i =1; i <= n;i++){ f[i]= g[i-1]+ nums[i-1]; g[i]=max(g[i-1],f[i-1]);}returnmax(f[n],g[n]);}};打家劫舍 II
题目：
分析题目
本题主要和上一题不同的是，收尾相连了，那么就进行特殊处理下第一个位置：
那么在上一题的基础上处理第一个位置：
- 将一个线性的数组根据题意（第一个位置选 / 不选的情况）分成两份：
- 那么具体如下图
- 第一个位置选的时候就代表数组下标 1 和 n-1 两处是不选的，再从 2 ~ n - 2 范围内找到最大值即可
- 如果第一个位置不选，那么就是从 1 ~ n - 1 范围内找到最大值
通过上述对一个的位置的特殊的特殊处理从而完成找到原本连续的数值中最大的值
题解核心逻辑
classSolution{public:introb(vector<int>& nums){int n = nums.size();if(n ==1)return nums[0];returnmax(nums[0]+rob1(2,n-2,nums),rob1(1,n-1,nums));}introb1(int l,int r,vector<int> nums){if(l > r)return0;int n = nums.size(); vector<int>f(n); vector<int>g(n); f[l]= nums[l];for(int i = l +1; i<=r;i++){ f[i]= g[i-1]+ nums[i]; g[i]=max(f[i-1],g[i-1]);}returnmax(f[r],g[r]);}};//引入虚拟节点：classSolution{public://因为这会有前后连接的问题，那么将他划分为两块进行分别的打家劫舍introb1(vector<int>& nums,int left,int right){int n = right +1; vector<int>f(n+1); vector<int>g(n+1);for(int i = left +1; i <= n;i++){ f[i]= g[i-1]+ nums[i-1]; g[i]=max(f[i-1],g[i-1]);}returnmax(f[n],g[n]);}introb(vector<int>& nums){int n = nums.size();//对第一个位置进行特殊处理：//选择第一个位置时：nums[0] + nums2 ~ n-2 的最大值（这里因为选择了第一个值后其左右都是不可选的了那么就不进行找最大值）//不选则第一个位置时：nums1 ~ n-1 的最大值 returnmax(rob1(nums,2,n-2)+ nums[0],rob1(nums,1,n-1));}};删除并获得点数
题目：
分析题目
根据示例1就能很好的理解：
再例如下图（当选择5后就会删除其5-1=4和5+1=6的数）：
最终结果：
注意本题就体现了画图的重要性，当你画图分析后，你就能一定的看出打家劫舍的影子！
所以本题解题思路：
- 本题可以通过新增一个数组，将出现的情况都存到这些数组中
然后在这个数组中进行一个打家劫舍问题的分析，最终就得到了答案，具体如下：
（为什么这样想呢，因为通过本题的分析，类似的想到打家劫舍中的不能访问相邻情况，那么如何还原打家劫舍呢，那么就能通过一个数组的形式，重新进行排序组合）
题解核心逻辑
那么通过一个数组的转换，将上述的问题转换成了打家劫舍问题：
- 状态表示：
- f[i]：选择 i 位置的最大价值
- 状态转移方程：
- f[ i ] = g [ i - 1] + arr[ i ]，也就是不选 i - 1的最大价值
- 初始化：
- 因为 num[ i ] != 0，那么就不用新建一个虚拟节点
- 对于选 i 位置来说，i = 0 则直接将f [ 0 ] 下标的值置为0（价值为0/为arr[0]）
- 对于不选的话，那就没意义同样为0
- 所以不用初始化，但需要创建一个新表arr，存储内部内容
- 填表顺序，从1开始从左往右到
返回值：选择 或 不选择最后一个位置的最大值（需要一个valmax标记位）
g[ i ] = max(f[ i- 1],g[ i - 1])，不选 i 位置，那么就是等于 选 i - 1 位置 或者 不选 i - 1位置的最大价值
g[i]：不选 i 位置的最大价值
classSolution{public:conststaticint N =10010;int arr[N]={};int f[N]={},g[N]={};intdeleteAndEarn(vector<int>& nums){int valmax =0;for(auto x : nums){ arr[x]+= x; valmax =max(valmax,x);}for(int i =1; i <= valmax ;i++){// cout << dp[i] << endl; f[i]= g[i-1]+ arr[i]; g[i]=max(f[i-1],g[i-1]);}returnmax(f[valmax],g[valmax]);}};//容器写法classSolution{public:conststaticint N =20010;int dp[N]={};intdeleteAndEarn(vector<int>& nums){//通过一个数组记录每个元素出现的次数，因为需要计算选择它时的最大价值int maxval =0;for(auto v : nums){ dp[v]+= v;//将每个值出现的总和 maxval =max(maxval,v);//找到出现的最大值（作为循环终点）}//得到一个新数组 dp，并且存着每个值的总和//在新dp中进行打家劫舍 vector<int>f(maxval+1);//f[i]：选择第 i 个位置的最大价值 vector<int>g(maxval+1);for(int i =1;i <= maxval;i++){ f[i]= g[i-1]+ dp[i];//这里是 i 而非 i - 1 是因为dp[1]是第一个位置，而之前i-1是因为arr[0]是第一个位置 g[i]=max(f[i-1],g[i-1]);}returnmax(f[maxval],g[maxval]);}};粉刷房子
题目：
分析题目
对于题目给的二维数组的含义是：
- 纵坐标代表：房子的下标
- 横坐标代表：颜色
- 其中注意的是相邻房子的颜色不能相同
要求的是在上述条件下的最低花费成本
题解核心逻辑
- 状态表示：
- 根据：经验 + 题目要求（本题同样是一个线性dp）
- 当涂到i为止的时候的最低消费
- 但有三种情况可以选，那么就需要二维 dp
- dp[i][0]：分刷到 i 位置的时候，最后一个位置刷上了 红色，此时的最小花费
- 状态转移方程
- 初始化：保证填表不越界
- 添加一个虚拟节点，让原本要初始化的值放入填表过程中
- 填表顺序
- 从左往右，一次填写三个表
- 返回值：最后一个位置的最小值（注意下标映射为了n）
注意事项：虚拟节点的初始化保证后续填表是正确的和原数组的下标关系
本质就是当选择了一个颜色后选择该颜色的最小值怎么算：也就是从前 i - 1个中选择不是该颜色的最小值即可：
…
classSolution{public:intminCost(vector<vector<int>>& costs){int n = costs.size(); vector<vector<int>>dp(n +1,vector<int>(3));//需要多开一行for(int i =1;i<=n;i++){ dp[i][0]=min(dp[i-1][1],dp[i-1][2])+ costs[i-1][0];//注意需要 - 1，因为dp多开了一行 dp[i][1]=min(dp[i-1][0],dp[i-1][2])+ costs[i-1][1]; dp[i][2]=min(dp[i-1][1],dp[i-1][0])+ costs[i-1][2];}returnmin(min(dp[n][0],dp[n][1]),dp[n][2]);}};这题本质也能分成三个颜色的三个数组，当然前面的两个数组的打家劫舍也能变成二维的:
上一题的二维版本：
中途总结🤓🤓🤓
通过上面的几道题我们可以知道：
当遇到类似打家劫舍的多状态dp时我们可以通过多个dp来保存他们各自的状态，并相互的使用dp来算出最终答案
- 按摩师中的多状态：预约和不预约两种状态
- 打家劫舍II和删除并获得点数这两题的多状态：则是在简单的打家劫舍上进行了一定的改变（分别使用到了特殊处理和hash）
- 而粉刷房子呢则是在前面都是两种互斥的状态下引入了三状态的情况，从而也就是进一步的对打家劫舍的多状态进行了提升，认识多状态不仅仅只是互斥的打家劫舍的两种状态，而是可以是不同的多种状态组成，通过分析多种状态相互的关系推出状态转移方程
下面就将继续多状态dp问题了，不再是打家劫舍而是股票问题，这类问题也就是经典的多状态问题
买卖股票的最佳时机含冷冻期
题目：
分析题目
通过题目 和 实例分析出，如下过程：
题解核心逻辑
- 状态表示：经验 + 题目要求
- 首先肯定是以 i 位置为结尾时的最大利润
- 但其中它可能会有多种状态，所以就还需要3行来表示状态：“买入”、“可交易”、“冷冻期”。
- dp[ i ][ 0 ]：第 i 天结束之后，处于“买入”状态，此时的最大利润
- dp[ i ][ 1 ]：第 i 天结束之后，处于“可交易”状态，此时的最大利润
- 首先肯定是以 i 位置为结尾时的最大利润
- 状态转移方程：
dp[i][0] = max( dp[i-1][0],dp[i-1][1] - price[i] )dp[i][1] = max(dp[i-1][1],dp[i-1][2])dp[i][2] = dp[i-1][0] + price[i]- 具体分析下这三种状态相互间的关系如下（状态机）
- 其中“买入”状态：当前是已经买入了股票了，可以卖出
- 初始化：
- 要处于“买入”状态，就需要得买入：dp[0][0] = -p[0]
- 要处于“可交易”，啥也不干：dp[0][1] = 0
- 要处于“冷冻期”，买了又卖价值为0：dp[0][2] = 0
- 填表顺序：从左往右，一次填写三个表
- 返回值，不要考略第一种“买入”状态，也就是 max（dp[n-1][1],dp[n-1][2]）
“可交易”：可以买入股票的状态、“冷冻期”：卖出股票了
dp[ i ][ 2 ]：第 i 天结束之后，处于“冷冻期”状态，此时的最大利润
classSolution{public:intmaxProfit(vector<int>& prices){int n = prices.size(); vector<vector<int>>dp(n,vector<int>(3));// dp[ i ][ 0 ]：处于“买入”状态，此时的最大利润（买入了某只股的在状态）// dp[ i ][ 1 ]：处于“可交易”状态，此时的最大利润（可买入的状态）// dp[ i ][ 2 ]：处于“冷冻期”状态，此时的最大利润//初始化： dp[0][0]=-prices[0];//这里表示的是让第0天的买入状态，那么利润就为买入当天价格（因为是买入所以为负） cout <<-prices[0]<< endl;for(int i =1;i < n;i++)//从1开始，第一个位置已经初始化完了{ 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];//等于 买入状态 + 卖掉股票后的值}returnmax(dp[n-1][1],dp[n-1][2]);//返回最后一天的值}};//换种理解方法：classSolution{public:intmaxProfit(vector<int>& prices){int n = prices.size(); vector<vector<int>>dp(n +1,vector<int>(3));//开辟 (N+1) * 3 的dp 多开一个位置让i和天数对齐方便理解//dp[i][0]：第i天处于买入状态时，能获取的最大利润//dp[i][1]：第i天处于卖出状态时，能获取的最大利润//dp[i][2]：第i天处于冷冻状态时，能获取的最大利润//初始化 dp[1][0]=-prices[0];//第一天买入状态则减去第一天的价格 dp[1][1]= dp[1][2]=0;//不可能为卖出和冷冻故默认为0for(int i =2;i <= n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][2]- prices[i-1]);//要么从冷冻期，要么保持不动选择前一天 dp[i][1]= dp[i-1][0]+ prices[i-1];//卖出 dp[i][2]=max(dp[i-1][1],dp[i-1][2]);//冷冻期：看保持自身不变还是从卖出过来 这里比较拗，但可以理解成冷冻期是可以继承前面的冷冻期或者从卖出状态过来的，所以进行判断 }returnmax(dp[n][0],max(dp[n][1],dp[n][2]));}};买卖股票的最佳时机含手续费
题目：
分析题目
- 交易次数无限，但每次都有手续费（买入和卖出只用出一次手续费）
- 若手里有股票就不能再买了
通过上述两个约束，分析实例1：
实例2：
题解核心逻辑
- 状态表示：
- 经验 + 题目要求
- dp[i]表示：第 i 天结束之后能获得的最大利润，因为需要考虑两种状态：“买入”、“卖出”
- 将dp表变成两张表：
- f[ i ]：第 i 天结束之后，处于“买入”状态，此时的最大利润
- 状态转移方程:
- 对于多状态的情况，可以画下图来进行分析：
- 最终得出：
- f[i] = max(f[i-1],g[i-1] - price[i])
- g[i] = max(g[i-1],f[i-1] + price[i] - fee)
- 初始化：
- 第0天买入状态，那么第0天买入即可：f[ 0 ] = -p[0]
- 第0天卖出状态，不操作即可：g[0] = 0
- 填表顺序：从左往右，两个表一起填
- 返回值：最大利润一定是在g[n-1]里面，因为f中还有股票没卖肯定不是最大利润
g[ i ]：第 i 天结束之后，处于“卖出”状态，此时的最大利润
classSolution{public:intmaxProfit(vector<int>& prices,int fee){int n = prices.size(); vector<int>f(n); vector<int>g(n); f[0]=-prices[0];for(int i =1;i<n;i++){ f[i]=max(f[i-1],g[i-1]- prices[i]); g[i]=max(f[i-1]+ prices[i]- fee,g[i-1]);}return g[n-1];}};买卖股票的最佳时机 III
题目：
分析题目
分析题目，提出注意点：
- 最多只能完成两笔交易
只能卖了股票，才能买新股票
分析实例1：
分析出有两种方法，都能解决：
1：第一种方法
2：第二种方法
再有两个例子：
题解核心逻辑
- 状态表示：经验 + 题目要求
- 粗力度的了解：dp[i] 第 i 天结束之后，所能获得的最大利润
- 使用一维还是二维还是根据能否通过一维就表示成功，若能就能使用若不能则使用二维，本题就需要二维的形式来表示，本题总共有四个状态所以原本是需要三维数组来存储，但不方便理解，所以换成二个二维的数组，其中单独出来的两个二维本质是一种状态的两种形式，该状态只有两种形式所以就能通过两种数组直接表示，避免使用三位数组
- f[ i ][ j ]：第 i 天结束之后，完成了 j 次交易，此时处于 “买入” 状态下的最大利润
- 状态转移方程：
f[ i ][ j ] =max( f[i-1][j]，g[i-1][j] - p[i])g[ i ][ j ] = max(g[ i - 1 ][j] ,f[ i - 1 ][ j - 1 ] + p[i] )
- 初始化：
- 通过状态转移方程可知，我们要防止 i - 1 和 j - 1，当i、j等于 0 时导致的越界问题
- 但其中发现只有一处用到了 j - 1
- 所以对于 f[ i - 1 ][ j - 1 ] 这里的 j - 1特殊处理下，就不用单独进行初始化了
- 如下图：本质就是将 j - 1 进行一个判断
- 先默认
g[i-1][j]是一定存在的，将他赋值给当前的g[i][j]
判断一下 j - 1 是否符合条件，若符合才在进行进一步的判断！
所以仅仅只需要操作 f 和 g 数组的第一行：
对买入和卖出两种状态进行分析（画出如下图情况）
g[ i ][ j ]：第 i 天结束之后，完成了 j 次交易，此时处于 “卖出” 状态下的最大利润
通过状态转移分析：
对于 第 0 天执行 1 2 笔交易是不能能存在的，所以将他设置为 负无穷小（INF -0x3F3F3F3F)代表无效，因为此处是进行一个取较大值，设为无穷小就肯定不会影响而对于 0 0 位置也就是 第 0 天 执行0笔交易的买入状态（f）的最大利润，此时因为是买入状态所以值只能是 -p[0] 也就是买入了当天的股票所以是负值
而对于 … 卖出状态（可交易状态），此时因为是第0天所以不可能有前面的利润所以只能是0
- 填表顺序：
- 从上往下，从左往右，同时填写两个值
- 最大值：
- 并不是g[ n - 1][ j - 1 ]
- 因为最大利润可能是在交易 0 ~ j - 1 次数上出现
- 所以应该是 g 表最后一行里面的最大值 g[ i ][ 0 ~ j - 1]
classSolution{public:intmaxProfit(vector<int>& prices){int n = prices.size(); vector<vector<int>>f(n +1,vector<int>(3,-0x3F3F3F3F)); vector<vector<int>>g(n +1,vector<int>(3,-0x3F3F3F3F)); g[0][0]=0;for(int i =1;i <= n;i++){for(int j =0;j <=2;j++){ f[i][j]=max(f[i-1][j],g[i-1][j]- prices[i-1]); g[i][j]= g[i-1][j];if(j -1>=0) g[i][j]=max(g[i-1][j],f[i-1][j-1]+ prices[i-1]);//注意是在从买入状态 变成 卖出状态时 才完成了交易，交易数才发生改变}}int res = INT_MIN;for(int j =0; j <=2;j++){ res =max(g[n][j],res);//看第n天}return res;}};再次总结：🤔🤔🤔
本题买卖股票最佳时机III他就是一个非常能体现多状态性的题目，本题通过状态表示可以看出需要的状态非常多若直接看：
第i天，处于买入/卖出状态，购买了j次，此时能获得的最大价值（这里足足有四个状态就代表需要三维数组来表示）
而三维是非常不好控的所以：
- 通过将买入和卖出状态分开成两个表从而降一维变成三种状态的二维数组即可控制
- 然后再计算过程中结合两个表进行计算得出答案
买卖股票的最佳时机 IV
本题本质和上一题几乎完全一样相信你理解了上一题这一题也没问题，那么也就直接给结果了：
classSolution{public:intmaxProfit(int k, vector<int>& prices){int n = prices.size(); vector<vector<int>>f(n +1,vector<int>(k +1,-0x3F3F3F3F)); vector<vector<int>>g(n +1,vector<int>(k +1,-0x3F3F3F3F)); g[0][0]=0;for(int i =1;i <= n;i++){for(int j =0;j <= k;j++){ f[i][j]=max(f[i-1][j],g[i-1][j]- prices[i-1]); g[i][j]= g[i-1][j];if(j -1>=0) g[i][j]=max(g[i-1][j],f[i-1][j-1]+ prices[i-1]);//注意是在从买入状态 变成 卖出状态时 才完成了交易，交易数才发生改变}}int res = INT_MIN;for(int j =0; j <= k;j++){ res =max(g[n][j],res);//看第n天}return res;}};最后总结：⭐⭐⭐
通过上述8道由浅到深的多状态问题包含打家劫舍和股票问题后，这里进行一定性的总结帮助大家and我复习和回顾
- 打家劫舍主要涉及到：互斥的多状态问题，也就是选择or不选择的问题，此处一般有两种状态，也是一种线性dp，当我们画出图后一般称下方式
其中灵魂在于：当选择了 i 位置 那么就代表 i - 1位置就是不选的了，而 i - 1 不选的值是已经填写好的所以可以直接使用
线性分析：
2. 一般来说会分成两个数组来看:
- 其中上面的这种是最基础的情况，也是我们看是否是打家劫舍的最基础框架，所以说当我们发现一个数组中它出现互斥的两种情况的时候就能一定的考略到使用这种dp
- 而在到后续的《粉刷房子》这道题引出了多状态的影子，也就是通过红色、蓝色、绿色不同的三种颜色且相互互斥的情况衍生出多个dp进行分别表示，同时也将打家劫舍原本的将dp分开的形式结合在了一起通过一个二维的dp[i][j]在列中通过3个位置分别表示红蓝绿，也为后续的股票问题进行了铺垫保证理解
- 再到后续的股票问题（最大利润 + 天数 + 买入/卖出），分别不断的引入多种状态：
- 冷冻期
- 手续费
- 最佳时机（限制次数）
其中最主要的在于先写出状态表示 如：f [ i ][ j ]：第 i 天结束之后，完成了 j 次交易，此时处于 “买入” 状态下的最大利润、dp[ i ][ 2 ]：第 i 天结束之后，处于“冷冻期”状态，此时的最大利润
- 当得出了状态表示后：进行分析状态得出状态转移方程，而状态分析也有技巧：
通过将状态一一列出来进行分析，它们相互的关系
冷冻期：
最佳交易
- 其中还想强调一点：也就是当我们发现我们写出来的状态表示中的状态超过了3种后，就可以通过将其中的一个状态单独出来将原本一个数组的截成两个数组，这分别体现在：
- 打家劫舍：选择 / 不选择 这个状态分成了两个dp（目的分成好理解好教学，基础理解多状态）
- 买卖股票最佳时机：买入 / 卖出 分成了两个dp（好处将原本四个状态需要三维数组的分成了两个二维）
