1. 题⽬链接：123.买卖股票的最佳时机III 

2. 题⽬描述：

3. 解法（动态规划）：

算法思路：

1. 状态表⽰：

对于线性dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：

        i. 以某个位置为结尾，巴拉巴拉；

        ii. 以某个位置为起点，巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰： 由于有「买⼊」「可交易」两个状态，因此我们可以选择⽤两个数组。但是这道题⾥⾯还有交易次 数的限制，因此我们还需要再加上⼀维，⽤来表⽰交易次数。其中：

        ▪ f[i][j] 表⽰：第i 天结束后，完成了j 次交易，处于「买⼊」状态，此时的最⼤利 润；

        ▪ g[i][j] 表⽰：第i 天结束后，完成了j 次交易，处于「卖出」状态，此时的最⼤利 润。

2. 状态转移⽅程：

对于f[i][j] ，我们有两种情况到这个状态：

        i. 在i - 1 天的时候，交易了j 次，处于「买⼊」状态，第i 天啥也不⼲即可。此时最 ⼤利润为： f[i - 1][j] ；

        ii. 在i - 1 天的时候，交易了j 次，处于「卖出」状态，第i 天的时候把股票买了。此 时的最⼤利润为： g[i - 1][j] - prices[i] 。

综上，我们要的是「最⼤利润」，因此是两者的最⼤值： f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]) 。 对于g[i][j] ，我们也有两种情况可以到达这个状态：

        i. 在i - 1 天的时候，交易了j 次，处于「卖出」状态，第i 天啥也不⼲即可。此时的 最⼤利润为： g[i - 1][j] ；

        ii. 在i - 1 天的时候，交易了j - 1 次，处于「买⼊」状态，第i 天把股票卖了，然 后就完成了j ⽐交易。此时的最⼤利润为： f[i - 1][j - 1] + 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]);

3. 初始化：

由于需要⽤到i = 0 时的状态，因此我们初始化第⼀⾏即可。

        ◦ 当处于第0 天的时候，只能处于「买⼊过⼀次」的状态，此时的收益为-prices[0] ，因 此f[0][0] = - prices[0] 。

        ◦ 为了取max 的时候，⼀些不存在的状态「起不到⼲扰」的作⽤，我们统统将它们初始化为- INF （⽤INT_MIN 在计算过程中会有「溢出」的⻛险，这⾥INF 折半取 0x3f3f3f3f ，⾜够⼩即可）

4. 填表顺序：

从「上往下填」每⼀⾏，每⼀⾏「从左往右」，两个表「⼀起填」。

5. 返回值：

返回处于「卖出状态」的最⼤值，但是我们也「不知道是交易了⼏次」，因此返回g 表最后⼀⾏ 的最⼤值。  

C++算法代码： 

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int n=prices.size();
        //边缘情况
        if(n==1)
        {
            return 0;
        }
        //建表
        vector<vector<int>>f(n,vector<int>(3,-0x3f3f3f));
        vector<vector<int>>g(n,vector<int>(3,-0x3f3f3f));
        //初始化
        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]);
                if(j>=1)
                {
                    g[i][j]=max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }
                else
                {
                    g[i][j]=g[i-1][j];
                }
            }
        }
        //找到最大利润
        int ret=0;
        for(int i=0;i<3;i++)
        {
            ret=max(ret,g[n-1][i]);
        }
        return ret;
    }
};

Java算法代码：

class Solution
{
	public int maxProfit(int[] prices)
	{
		// 1. 创建 dp 表 
		// 2. 初始化 
		// 3. 填表 
		// 4. 返回值 
		int INF = 0x3f3f3f3f;
		int n = prices.length;
		int[][] f = new int[n][3];
		int[][] g = new int[n][3];
		for (int j = 0; j < 3; j++) f[0][j] = g[0][j] = -INF;
		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] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
				g[i][j] = g[i - 1][j];
				if (j - 1 >= 0) // 判断状态是否存在 
					g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
			}
		int ret = 0; // 赵楚最后⼀⾏的最⼤值 
		for (int j = 0; j < 3; j++) ret = Math.max(ret, g[n - 1][j]);
		return ret;
	}
}