题目链接：

一、题目解析

题目：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;}
};