代码随想录算法训练营第50天 | 123.买卖股票的最佳时机III, 188.买卖股票的最佳时机IV

123.买卖股票的最佳时机III

代码随想录链接

题目

LeetCode-123.买卖股票的最佳时机III

由LeetCode-122.买卖股票的最佳时机II的不限制买入卖出次数变成了限制可以买卖两次, 求最大利润.

题目分析

动态规划依然是不同时刻状态与状态之间的推算.

动态规划五部曲:

• 确定dp数组及下标含义

  本题中每一天有五种状态, 分别是一次没买, 第一次买了持有, 第一次买了已卖出, 第二次买了持有, 第二次买了已卖出.

  dp[i][0-4]分别表示第i天的以上五种状态.

• 确定递推公式

  如果一次没买, 那么就不会有资金变动, 所以dp[i][0] = 0对所有i都适用.

  第i天的第一次买入持有的状态可以从第i-1天的一次没买和买了持有的状态推出; 第i天的第一次买入并卖出的状态也可以由前一天的第一次买了持有的状态和第一次买了且卖出的状态推出; 剩下两个状态同理.

  \[dp[i][0] = 0\] \[dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])\] \[dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])\] \[dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])\] \[dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4])\]

• dp数组的初始化

  由于是求最大值且数据都是正整数, 故所有位都可以初始化为0.

  由于并没有限制买入和卖出操作不能在同一天完成, 所以第一天的五中状态可以初始化为:

  dp[0][0] = 0;
  dp[0][1] = -prices[0];
  dp[0][2] = 0;
  dp[0][3] = -prices[0];
  dp[0][4] = 0;

• 遍历顺序

  由于递推公式中每一天的状态都由前一天的状态决定, 故一定是从前先后遍历

题解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = 0;
            dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
            dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
            dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
        }
        return max(dp.back()[2], dp.back()[4]);
    }
};

188.买卖股票的最佳时机IV

代码随想录链接

题目

LeetCode-188.买卖股票的最佳时机IV

由上面的题目扩展而来, 变成了最多买卖给定的k次.

题目分析

其实就是把上面的题目扩展了一下, 题目分析都是一样的, 同一天的dp数组的奇数位上都是买入并持有的状态, 偶数位上都卖出状态.

题解

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
        for (int i = 1; i < 2 * k + 1; i+=2) // 初始化第一天的所有买入状态
            dp[0][i] = -prices[0];
        for (int i = 1; i < prices.size(); i++) // 递推求每一天的状态
            for (int j = 0; j < k; j++) {
                dp[i][2 * j + 1] = max(dp[i - 1][2 * j] - prices[i], dp[i - 1][2 * j + 1]);
                dp[i][2 * j + 2] = max(dp[i - 1][2 * j + 1] + prices[i], dp[i - 1][2 * j + 2]);
            }
        int maxVal = 0;
        for (int i = 0; i < dp.back().size(); i+=2) {   // 求最后一天所有卖出状态的最大值
            if (dp.back()[i] > maxVal)
                maxVal = dp.back()[i];
        }
        return maxVal;
    }
};