动态规划专练:力扣第123、188题

力扣第123题-买卖股票的最佳时机Ⅲ

1.本题的难点在于如何处理“2次买卖”，还是可以将当天的状态分为4种：

（1）第一次持有股票。要么是之前已经买入，要么是之前没有而当天买入，递推公式为dp[1][0] = fmax(dp[0][0], -prices[i])。

（2）第一次未持有股票。要么是之前就已经卖出，要么是之前持有今天卖出，递推公式为dp[1][1] = fmax(dp[0][1], dp[0][0] + prices[i])。

（3）第二次持有股票。从第二次开始的状态就需要建立在“完成了第一次买卖”之上来考虑，要么是第一次卖出后在今天以前已经买入，要么是之前没有而当天买入，递推公式为：dp[1][2] = fmax(dp[0][2], dp[0][1] - prices[i])。

（4）第二次未持有股票。要么是之前就已经卖出第二次的股票，要么是之前持有今天卖出，递推公式为dp[1][3] = fmax(dp[0][3], dp[0][2] + prices[i])。

2.基于以上思想，可写出完整代码如下：

1. int maxProfit(int* prices, int pricesSize) { 2. // dp[0][0]：当前持有第1支股票 3. // dp[0][1]：卖出第1支股票，完成1笔交易 4. // dp[0][2]：当前持有第2支股票 5. // dp[0][3]：卖出第2支股票，完成2笔交易 6. int dp[2][4]; 7. // 初始化第0天四种状态 8. dp[0][0] = -prices[0]; // 第一天买入第一支 9. dp[0][1] = 0; // 不可能卖出，收益0 10. dp[0][2] = -prices[0];// 当天买入再卖出再买入第二支，等价直接买 11. dp[0][3] = 0; // 不可能完成两次卖出 12. 13. for (int i = 1; i < pricesSize; i++){ 14. // 状态0：第一次持有，要么之前就持有，要么今天刚买入 15. dp[1][0] = fmax(dp[0][0], -prices[i]); 16. // 状态1：第一次卖出，要么之前已卖出，要么今天卖出第一次持仓 17. dp[1][1] = fmax(dp[0][1], dp[0][0] + prices[i]); 18. // 状态2：第二次持有，要么之前持有第二支，要么第一次卖出后今天买入 19. dp[1][2] = fmax(dp[0][2], dp[0][1] - prices[i]); 20. // 状态3：第二次卖出，要么之前完成两笔，要么今天卖出第二次持仓 21. dp[1][3] = fmax(dp[0][3], dp[0][2] + prices[i]); 22. 23. // 更新前一天状态为当前天，滚动数组压缩空间 24. dp[0][0] = dp[1][0]; 25. dp[0][1] = dp[1][1]; 26. dp[0][2] = dp[1][2]; 27. dp[0][3] = dp[1][3]; 28. } 29. 30. // 最多两次交易，最大收益一定是完成两次卖出的状态 31. return dp[0][3]; 32. }

该算法时间复杂度为O(n)，空间复杂度为O(1)。

力扣第188题-买卖股票的最佳时机Ⅳ

1.本题相比于力扣第123题-买卖股票的最佳时机Ⅲ，区别仅在于将允许买卖的次数从2次变为了k次，本质还是没有变，只需要设置2k个状态来记录第k次持有/未持有时的最大金额。递推公式也都是从上一个状态中得到的。完整代码如下：

1. int maxProfit(int k, int* prices, int pricesSize) { 2. // dp[0][j*2]：持有第j+1次买入的股票 3. // dp[0][j*2+1]：完成第j+1次完整交易（已卖出） 4. // 滚动数组dp[2][2k]，只保存前一天和当天状态 5. int dp[2][k * 2]; 6. // 第0天初始化所有交易状态 7. for (int i = 0; i < k; i++){ 8. dp[0][i * 2] = -prices[0]; // 当天买入第i+1笔 9. dp[0][i * 2 + 1] = 0; // 无法卖出，收益为0 10. } 11. 12. // 从第2天开始遍历价格数组 13. for (int i = 1; i < pricesSize; i++){ 14. // 遍历k次交易的两种状态 15. for (int j = 0; j < k; j++){ 16. if (j == 0) { 17. // 第一次持仓：之前持有 或 今日首次买入 18. dp[1][0] = fmax(dp[0][0], -prices[i]); 19. } else { 20. // 非首次持仓：之前持有该笔 或 上一笔卖出后今日买入 21. dp[1][j * 2] = fmax(dp[0][j * 2], dp[0][j * 2 - 1] - prices[i]); 22. } 23. // 第j+1次卖出：之前已完成该笔交易 或 今日卖出当前持仓 24. dp[1][j * 2 + 1] = fmax(dp[0][j * 2 + 1], dp[0][j * 2] + prices[i]); 25. 26. // 滚动更新前一天状态为当天状态 27. dp[0][j * 2] = dp[1][j * 2]; 28. dp[0][j * 2 + 1] = dp[1][j * 2 + 1]; 29. } 30. } 31. 32. // 最大收益为最多k次交易全部卖出的状态 33. return dp[0][k * 2 - 1]; 34. }

该算法时间复杂度为O(n * k)，空间复杂度为O(k)。