动态规划：17.简单多状态 dp 问题_买卖股票的最佳时机III_C++
题目链接：
一、题目解析
题目：123. 买卖股票的最佳时机 III - 力扣（LeetCode）
解析：
拿示例1举例：
我们可以如图所示买入卖出股票，以求得最大利润，并且交易次数不超过2次
拿示例3举例：
不管我们怎么买，最终我们利润总会是负数，所以交易次数为0
二、算法原理
1、状态表示
我们在状态表示的时候，一般都会创建一个数组dp，也就是我们所说的dp表，我们要做的就是把每一个状态的值填入这个表内，最终这个表内的某一个值可能就是我们要返回的值。
状态简单理解就是dp表内某一个值代表的含义。
如何确定状态表示
- 题目要求
简单的题目里一般会给出
- 经验+题目要求
越学越深入，动态规划也是熟能生巧，在题目中没有明显给出的时候，我们就要凭借自己做题的经验来确定，所以就需要我们大量的做题。
- 分析问题的过程中，发现重复子问题
分析问题的过程中把重复子问题抽象成我们的状态表示，这个更难理解，一切的基础都是我们先对动态规划算法熟练运用。我也不懂，我们慢慢来。
综上：我们通常会以一个位置为结尾或者开始求得我们想要的答案
那我们的这道题得状态表示是什么样的：
我们以一个位置为结尾来表示
状态暂时表示为：dp[i]：第i天结束之后所有的最大利润
2、状态转移方程
确定状态表示之后我们就可以根据状态标识推出状态转移方程
状态转移方程是什么？
不讲什么复杂的，简单来说状态转移方程就是 dp[i][j]等于什么 dp[i][j]=？
这个就是状态转移方程，我们要做的，就是推出dp[i][j]等于什么
我们根据状态表示再结合题目+经验去推理转移方程，这一步也是我们整个解题过程中最难的一步
我们在这道题先简单了解下什么是状态转移方程，之后比较难的题目再细推
状态转移方程推理：
我们这个题依然是有两个状态：买入和卖出
我们令买入状态为f[i]，卖出状态为g[i]，我们可以借此来表示两者之间的关系
但是，题目中说到，我们最多只能交易两次
所以我们可以在买入和卖出两个状态上加上天数
所以，买入表示为f[i][j]，卖出表示为g[i][j]
所以更为准确的状态表示为：
- f[i][j]:第i天结束后，交易j次后的买入的最大利润
- f[i][j]:第i天结束后，交易j次后的卖出的最大利润
我们画图来推理这两个状态之间的关系：
这里需要注意的是，我们为什么在买入到卖出时，需要买入状态交易次数减一的那次状态，因为我们由买入到卖出，这就是一次交易过程。
状态转移方程：
- f[i][j]=max(f[i-1][j],g[i-1][j]-price[i])
- g[i][j]=max(g[i-1][j],f[i-1][j-1]+price[i])
这里卖出状态有一点需要注意，虽然我们写出来其状态为g[i][j]=max(g[i-1][j],f[i-1][j-1]+price[i])
但是当交易次数为1的时候，我们需要给g[i-1][-1]的状态，但是这是不合法的，j必须大于等于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]+price[i]);
}
3、初始化
我们初始化的需要注意的有两个方面：
越界问题
当我们填第一天结束时的状态时，我们需要第0天的状态，但是没有第0天，那么填表时就会越界
我们就需要用初始化解决该问题
我们在第0天时，不可能完成一次或者两次交易，只能是0次，所以为了不让后面的值影响我们填表
我们需要对第0天的第一或者二次交易初始化为-∞
但是，我们在比较时，遇到-∞减去一个数，结果会溢出，因为-∞已经是最小的一个数了
所以我们在这里不能初始化为-∞，可以初始化为-0x3f3f3f3f
这个数能保证我不影响我们填表的同时，又不至于我们结果溢出
下表映射问题
这里不需要注意什么
4、填表顺序
从做到右，从上到下，两个表同时填写
5、返回值
由于我们最后一天一定是卖出状态才会使利润到达最大，所以我们只需比较最后一天卖出状态的三个交易次数就可以了
三、编写代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int INF=0x3f3f3f3f;
int n=prices.size();
vector<vector<int>> f(n,vector<int>(3,-INF));
auto g=f;
f[0][0]=-prices[0];
g[0][0]=0;
for(int i=1;i<n;i++)
{
for(int j=0;j<3;j++)
{
f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
g[i][j]=g[i-1][j];
if(j>=1)
g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]);
}
}
int ret=0;
for(int i=0;i<3;i++)
{
ret=max(ret,g[n-1][i]);
}
return ret;
}
};