「动态规划」买卖股票的最佳时机

力扣原题链接，点击跳转。

给定一个整数数组prices，prices[i]表示股票在第i天的价格。你最多完成2笔交易。你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。设计一个算法计算最大利润。

我们用动态规划的思想来解决这个问题。首先确定状态表示。我们用f和g分别表示「买入」和「卖出」状态（处于「买入」状态时，手里有股票；处于「卖出」状态时，手里没有股票）。用i表示第i天结束时的状态。用j表示当前完成了j笔交易。也就是说，用f[i][j]表示在第i天结束时，处于「买入」状态下，完成了j笔交易，此时的最大利润；用g[i][j]表示在第i天结束时，处于「卖出」状态下，完成了j笔交易，此时的最大利润。

接下来推导状态转移方程。首先考虑f[i][j]，如果第i-1天结束时处于「买入」状态，那么需要在第i天「持有股票」，就能在第i天结束时依然处于「买入」状态，由于「持有股票」并不会改变完成的交易次数，也不会改变利润，所以此时f[i][j]=f[i-1][j]；如果第i-1天结束时处于「卖出」状态，那么需要在第i天「买入股票」，就能在第i天结束时处于「买入」状态，由于「买入股票」并不会改变完成的交易次数，但是会使利润减少第i天的股票价格，所以此时f[i][j]=g[i-1][j]-prices[i]。由于要求的是最大利润，所以f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i])。

接着考虑g[i][j]，如果第i-1天结束时处于「买入」状态，那么需要在第i天「卖出股票」，就能在第i天结束时处于「卖出」状态，由于「卖出股票」后就完成了一次完整的交易，所以在第i-1天结束时的交易次数会比第i天结束时的交易次数少1，即第i-1天结束时的交易次数是j-1，同时「卖出股票」会使利润增多第i天的股票价格，所以此时g[i][j]=f[i-1][j-1]+prices[i]；如果第i-1天结束时处于「卖出」状态，那么需要在第i天「观望」，就会在第i天结束时依然处于「卖出状态」，而「观望」并不会改变交易次数和利润，所以此时g[i][j]=g[i-1][j]。由于要求的是最大利润，所以g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j])。

接下来考虑初始化的问题。再次观察状态转移方程：f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i])，g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j])。由于f[i][j]和g[i][j]都会依赖于i-1，所以初始化2个表的最上面一行。注意到j的取值范围是[0,2]，故需要初始化的坐标有：(0,0)、(0,1)和(0,2)。不过，(0,1)和(0,2)说明在第0天结束时已经至少完成了1笔交易，也就是说，会在第0天「买入后立刻卖出股票」，这种操作是没有意义的，因为浪费了交易次数。所以，为了让(0,1)和(0,2)的值不影响取max的结果，应该把这两个位置初始化为-∞，即-0x3f3f3f3f，注意不是INT_MIN，防止计算g[i-1][j]-prices[i]时溢出。所以，现在只需要考虑f[0][0]和g[0][0]。其中f[0][0]表示在第0天结束时处于「买入」状态，只需要在第0天「买入股票」，即f[0][0]=-prices[0]；g[0][0]表示在第0天结束时处于「卖出」状态，只需要在第0天「观望」，即g[0][0]=0。

还有另一个地方有可能越界。注意到g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j])，会依赖于j-1，所以理论上还需要初始化g表的最左边一列。但是这么做的话，会让f表和g表对应不上，导致细节问题更难处理。所以我们采取另一种方法。j代表的是交易次数，之所以j-1有可能越界，是因为这样算出来的交易次数是-1。既然不存在交易次数是-1的情况，我们只需要判断一下，如果j-1≥0，才计算g[i][j]=max(f[i-1][j-1]+prices[i],g[i-1][j])，否则g[i][j]=g[i-1][j]即可。这样，就不存在越界的风险了。

填表时应从上往下填每一行，每一行从左往右填，且f表和g表同时填。最终应返回g表的最后一行的最大值，这是因为要想获取最大利润，就一定要在最后一天结束时处于「卖出」状态，且不确定此时的交易次数。我们来分析一下dp表的规模。由于没有加上虚拟节点，所以行数应与实际天数相同，即prices的元素个数n；由于j的所有可能取值是0、1和2，所以有3列。综上，f表和g表的大小均为n×3。

class Solution {
public:int maxProfit(vector<int>& prices) {const int INF = 0x3f3f3f3f;int n = prices.size();// 创建dp表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 >= 0)g[i][j] = max(g[i][j], f[i-1][j-1] + prices[i]);}}// 求g表最后一行的最大值return *max_element(g[n-1].begin(), g[n-1].end());}
};

这道题还有个终极版本：力扣原题链接，点击跳转。

把限定的交易次数从2次改为k次，其余条件不变，求最大利润。

分析思路完全一样。状态表示和状态转移方程不变。初始化方式不变，依然是最上面一行除了f[0][0]=-prices[0]和g[0][0]=0之外都初始化为-∞。填表顺序不变。最后依然是返回g表最后一行的最大值。只有表的规模从n×3变为了n×(k+1)。

代码的话，只需要把上道题的代码的3修改为k+1即可。事实上，上道题就是本题中k=2时的特殊情况。除此之外，还有一个点值得优化，最多的交易次数一定不会超过总天数的一半，比如总天数是10天，那么最多交易5次；总天数是9天，那么最多交易4次。

class Solution {
public:int maxProfit(int k, vector<int>& prices) {const int INF = 0x3f3f3f3f;int n = prices.size();// 交易次数不会超过总天数的一半k = min(k, n/2);// 创建dp表vector<vector<int>> f(n, vector<int>(k+1, -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 < k+1; 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 >= 0)g[i][j] = max(g[i][j], f[i-1][j-1] + prices[i]);}}// 求g表最后一行的最大值return *max_element(g[n-1].begin(), g[n-1].end());}
};