摘要

• 只买卖一次股票，和不限制次数地买卖股票，只是在递推公式上有差别。而且，这两种情况都不需要记录完成买卖的次数。

• 指定了至多买k次股票，这就暗含着每天的状态信息要有买卖股票的次数。

LeetCode123 买卖股票的最佳时机III

123. 买卖股票的最佳时机 III - 力扣（Leetcode）

• 这题和前面两题买卖股票（代码随想录算法训练营打卡Day49）的区别还是买卖股票的次数。而这题的特点就是我们要控制至多买2次股票。

  • 至多买一次股票，和不限制次数地买卖股票，只是在递推公式上有差别。而且，这两种问题都不需要记录完成买卖的次数。
  • 但是，至多买2次股票，这就暗含着每天的状态信息要有买卖股票的次数。所以，这道题和前两题的除了在递推公式上有差别，在dp数组的定义上也有差别。

• 确定dp数组及数组下标的含义：

  • dp[i][j]表示的是第i天买卖股票可能获得的最大利润，
  • j == 0表示在第i天或第i天之前第一次买入了股票
  • j == 1表示在第i天或第i天之前第一次卖出了股票
  • j == 2表示在第i天或第i天之前第二次买入了股票
  • j == 3表示在第i天或第i天之前第二次卖出了股票

• 确定状态转移方程，假设一开始持有的金额为0

  • 对于第0天，

    • 对于第一次买卖股票，如果买入了股票，只可能是在第0天时买入股票，所以；如果卖出了股票，只能是第0天买入后再卖出，金额不变，。

    • 对于第二次买卖股票，也同理，如果买入了股票，只可能是在第0天时买入股票，所以；如果卖出了股票，只能是第0天买入后再卖出，金额不变，。

  • 对于第i天，先看第一次买卖

    • 如果买入了股票，说明在第i天或之前的某一天第一次买入了股票。
      • 如果是在第i天买入了股票，至少第i-1天时是未持有股票的，根据dp数组的定义，第i-1天持有的金额是dp[i-1][1]，那么第i天时持有的金额为；
      • 如果在之前的某一天买入了股票，现在还应该继续持有股票，所以 ，保持着持有之前买入的股票的状态。
    • 如果卖出了股票，说明在第i天或之前的某一天第一次卖出了股票。
      • 如果是在第i天买入了股票，至少第i-1天时是持有股票的，根据dp数组的定义，第i-1天持有的金额是dp[i-1][0]，那么第i天时持有的金额为；
      • 如果在之前的某一天卖出了股票，第i天还不应该买入股票，所以，保持之前的状态即可

  • 再看第二次买卖，因为题目明确说了不能同时参与多笔交易，所以第二次买卖必须在第一次买卖完成之后进行，所以第二次买入的状态是由第一次买卖完成的状态（即第一次卖出股票dp[i - 1][1]）转移来的。

    • 如果买入了股票，在第i天或之前的某一天第二次买入了股票。

      • 如果是在第i天买入了股票，至少第i-1天时是未持有股票的，可以假设第i-1天时已经完成了第一次买卖，根据dp数组的定义，第i-1天持有的金额是dp[i-1][1]，那么第i天时持有的金额为；
      • 如果在之前的某一天买入了股票，现在还应该继续持有股票，所以 ，保持着持有之前买入的股票的状态。

    • 如果卖出了股票，在第i天或之前的某一天第二次卖出了股票。

      • 如果是在第i天买入了股票，至少第i-1天时是持有股票的，根据dp数组的定义，第i-1天持有的金额是dp[i-1][0]，那么第i天时持有的金额为；
      • 如果在之前的某一天卖出了股票，第i天还不应该买入股票，所以，保持之前的状态即可

  • 状态转移方程
    

• 按推导出的第0天的状态来初始化dp数组。

• 遍历顺序，dp[i][j]的更新依赖于dp[i-1][j]，所以i应该从小到大遍历，第一次和第二次买卖股票有先后顺序，j应该从小到大更新。

题解代码如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
        dp[0][0] = 0 - prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0 - prices[0];
        dp[0][3] = 0;

        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], 0 - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
        }

        return dp[prices.size() - 1].back();
    }
};

LeetCode188 买卖股票的最佳时机IV

188. 买卖股票的最佳时机 IV - 力扣（Leetcode）

• 这题的解法其实就是动态地控制“买卖股票的最佳时机III”的中的最多买卖次数。最多买卖次数从两次变成了k次，实际上就是添加一个循环来表示从第j - 1次买卖到第j次买卖的状态转移。

• 确定dp数组及数组下标的含义：

  • dp[i][j]表示的是第i天买卖股票可能获得的最大利润，j为0或偶数时表示第j%2+1次持有股票，j为奇数时表示第j%2+1次卖出股票。

• 确定状态转移方程，关键在于每次买卖之间的状态转移

  • 第0天的初始化要注意，不能只初始化第一次买卖的状态，每次买卖都要初始化，

  

  • 对于第i天，如果是第一次买卖，假设一开始持有的金额为0

  

  • 对于第i天，如果不是第一次买卖，假设当前是第j%2+1次买卖，则第i天第j%2+1次买卖的买卖是由已经完成了j-1次买卖的状态转移来的

  

• 初始状态就是第0天的状态，按第0天的状态初始化dp数组。

• 遍历顺序的道理和上一题相同，i从小到大遍历，j也从小到大遍历。

题解代码如下

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k, 0));
        for (int j = 0; j < 2 * k; j += 2) {
            dp[0][j] = 0 - prices[0];
        }

        for (int i = 1; i < prices.size(); i++) {
            for (int j = 0; j < 2 * k; j += 2) {
                // 判断一下是不是第一次买卖股票，防止数组下标越界
                if (j == 0) dp[i][j] = max(dp[i - 1][j], 0 - prices[i]);
                else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }

        return dp[prices.size() - 1][2 * k - 1];
    }
};