动态规划专练:力扣第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]持有第j1次买入的股票 3. // dp[0][j*21]完成第j1次完整交易已卖出 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]; // 当天买入第i1笔 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. // 第j1次卖出之前已完成该笔交易 或 今日卖出当前持仓 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)。