摘要

• 贪心算法可以看作是动态规划的特例，可以使用贪心算法解决的问题往往都可以使用动态规划解决，而动态规划往往是解决一类问题的通法。
• 买卖股票的问题，通过添加一个维度来保存更详细的状态，即是否持有股票，来简化逻辑，达到用空间换时间的目的
• 通过递推公式的改变，来控制是只买卖一次股票，还是可以多次买卖股票。

LeetCode121 买卖股票的最佳时机

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

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

  • 根据之前的经验，最容易想到的dp数组是这样的：dp[i]表示到第i天（i从0开始）买卖股票获得的最大利润。但是这样定义dp数组是有缺点的，因为我们必须要先买入股票才能卖出股票，这样的dp数组并没有保存我们持有股票的状态，还需要额外的判断逻辑来知道当前是否持有股票，这样的dp数组才能进行更新。
  • 既然如此，为什么不试试把是否持有股票的状态信息也保存在dp数组中呢？对于第i天而言，我们要么就是持有股票，要么就是不持有股票。把是否持有股票的状态信息保存在dp数组中显然是可行的。
  • 所以这样来定义dp数组及下标的含义：dp[i][j]表示的是第i天买卖股票可能获得的最大利润，j==0时表示在第i天持有股票，j==1表示在第i天不持有股票。

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

  • 对于第0天，如果持有股票，只可能是在第0天时买入股票，所以；如果不持有股票，第0天是刚开始，说明前面也没有进行买卖股票的可能，金额不变，。

  • 对于第i天，

    • 如果持有股票，说明在第i天或之前的某一天买入了股票。
      • 如果是在第i天买入了股票，由于题目规定只能购买一次，所以之前没有进行过买卖，直接得到；
      • 如果在之前的某一天买入了股票，现在还应该继续持有股票，所以 ，保持着持有之前买入的股票的状态。
    • 如果不持有股票，说明在第i天或之前的某一天卖出了股票。
      • 如果是在第i天卖出了股票，由于题目规定只能卖出一次，所以之前没有进行过买卖，直接得到；
      • 如果在之前的某一天卖出了股票，由于题目规定只能卖出一次，所以之后也不再进行买卖股票，保持之前的状态即可

  • 状态转移方程
    

• 推导状态转移方程时，第0天对应的状态即为初始状态，按照第0天的推导初始化dp数组。

• dp[i][j]的更新依赖于dp[i-1][j]，所以i应该从小到大遍历，要先买入股票才能卖出股票，所以j也应该先0后1。

题解代码如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), {0, 0});
        dp[0][0] = 0 - prices[0];
        dp[0][1] = 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]);
        }

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

• 不过这题因为只买卖一次，所以可以很直观地看出贪心方法，尽量选股票最低价格时买入，选股票最高价格时卖出。

题解代码如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            buy = min(buy, prices[i]);
            result = max(result, prices[i] - buy);
        }
        return result;
    }
};

LeetCode122 买卖股票的最佳时机II

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

• 在代码随想录算法训练营打卡Day32中，使用了贪心法来解决本题，这次使用动态规划的思想来解决这道题。分析的过程和上一题类似，只是状态转移方程的变化，对应了可以多次买卖股票。

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

  • dp[i][j]表示的是第i天买卖股票可能获得的最大利润，j==0时表示在第i天持有股票，j==1表示在第i天不持有股票。

• 确定状态转移方程，假设一开始持有的金额为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天还不应该买入股票，所以，保持之前的状态即可

  • 状态转移方程
    

• 推导状态转移方程时，第0天对应的状态即为初始状态，按照第0天的推导初始化dp数组。

• dp[i][j]的更新依赖于dp[i-1][j]，所以i应该从小到大遍历，要先买入股票才能卖出股票，所以j也应该先0后1。

题解代码如下

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

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

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