动态规划 —— dp 问题-买卖股票的最佳时机III
江河入海，知识涌动，这是我参与江海计划的第9篇。
1. 买卖股票的最佳时机III
题目链接：
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
2. 题目解析
3. 算法原理
状态表示：以某一个位置为结尾或者以某一个位置为起点
dp[i]表示：第i天结束之后，此时的最大利润 ：两种情况：
1. f[i][j]表示：第i天结束之后，完成了j次交易，处于买入状态，此时的最大利润
2. g[i][j]表示：第i天结束之后，完成了j次交易，处于卖出状态，此时的最大利润
2. 状态转移方程
在第i-1天处于买入状态，看买入状态能不能到自己，看卖出状态能不能到买入状态，另一个状态也是如此，一共4种状态
买入状态到 卖出状态到 买入状态 什么都不干 -prices[i](买股票) 卖出状态 +prices[i](交易次数+1) 什么都不干 1. f[i][j] = max(f[i-1][j] , g[i-1][j] - prices[i])
2. g[i][j] = max(g[i-1][j] , f[i-1][j-1] + prices[i]
3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行
因为是在第i-1天处于买入/卖出状态，所以当交易次数为0时，就相当于在第i天为-1，那么就会导致越界
所以我们可以修改一下第二个状态转移方程来判断一下，我们可以看到卖出状态到自己的情况是不会改变的，所以只用修改买入状态到卖出状态 ：
1. g[i][j] = g[i-1][j]（此状态一定不会越界）
2. if(j-1>=0) g[i][j] = max(g[i][j] , f[i-1][j-1] + prices[i]
在查找f[i-1][j-1] + prices[i]状态的时候先判断一下 下标是否合法(if(j-1>=0))，然后再求max
定义一个正无穷大/小的时候涉及到需要进行加减操作的时候，不要使用INT_MIN/MAX，因为如果INT_MIN减去一个数的话就会变成一个非常大的整数而导致溢出，所以我们最好用 +/- 0x3f3f3f3f 来表示最小值
本题初始化就是先将表里的所有值都初始化为-无穷大，再把f[0][0] = --prices[0],g[0][0] = 0
4. 填表顺序
本题的填表顺序是：从上往下填写每一行，每一行从左往右，两个表同时填
5. 返回值 ：题目要求 + 状态表示
因为是要最大利润，所以买入状态不用考虑
本题的返回值是：g表里最后一行里面的最大值
4. 代码
动态规划的固定四步骤：1. 创建一个dp表
2. 在填表之前初始化
3. 填表（填表方法：状态转移方程）
4. 确定返回值
class Solution {public: const int INF=0x3f3f3f3f;//将无穷大赋予给INF int maxProfit(vector& prices) { int n = prices.size(); //1. 创建dp表 //3：交易次数的三列：0，1，2,再将所有的位置都变成负无穷大 vector<vector>f(n,vector(3,-INF)); auto g=f; //2. 在填表之前初始化 f[0][0]=-prices[0]; g[0][0]=0; //3. 填表（填表方法：状态转移方程） for(int i=1;i<n;i++) { for(int j=0;j=1) g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]); } } //g表里最后一行里面的最大值 int ret=0; for(int j=0;j<3;j++) ret=max(ret,g[n-1][j]); return ret; }};未完待续~
