121.买卖股票的最佳时机

题目链接 文章讲解 视频讲解

动规五部曲：

• dp[j][0]: 表示持有股票的最大现金，dp[j][1]表示不持有股票的最大现金
• 递推公式：
  • 第j天持有股票的最大现金为：之前就持有这只股票和今天持有这只股票取最大值：
    dp[j][0] = max(dp[j-1][0], -prices[j]);
  • 第j天不持有股票的最大现金为：之前就已经不持有和今天卖出这只股票取最大值：
    dp[j][1] = max(dp[j-1][1], dp[j-1][0] + prices[j])
• 初始化：第j天是否持有股票的最大值只取决于前一天是否持有股票，所以只需初始化第0天
  dp[0][0] = -prices[0]
  dp[0][1] = 0;
• 遍历顺序：从前向后遍历
• 打印dp数组

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2));

        dp[0][0] = -prices[0];
        dp[0][1] = 0;

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

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

122.买卖股票的最佳时机II

题目链接 文章讲解 视频讲解

思路：因为股票可以买入多次所以：当天持有股票dp[j][0]为前一天就持有股票和前一天不持有股票+今天才买入股票取最大值(如果只可以买入一次股票，那么初始现金一直都是0，所以买入股票后现金为-prices[j]，而现在的初始现金为dp[j-1][1]-prices[j]) 递推公式为：dp[j][0] = max(dp[j-1][0], dp[j-1][1]-prices[j]);
dp[j][1]：仍然是max(dp[j-1][1], dp[j-1][0]+prices-[j])

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // dp[j][0] 表示持有股票的最大价值，dp[j][1]表示不持有股票的最大价值
        vector<vector<int>> dp(prices.size(), vector<int>(2));

        // 递推公式: dp[j][0] = max(dp[j-1][0], dp[j-1][1]-prices[j]);
        // dp[j][1] = max(dp[j-1][1], dp[j-1][0] + prices[j]);

        // 初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for(int j = 1; j < prices.size(); ++j) {
            dp[j][0] = max(dp[j-1][0], dp[j-1][1]-prices[j]);
            dp[j][1] = max(dp[j-1][1], dp[j-1][0] + prices[j]);
        }
        
        for(auto vec : dp) {
            for(int val : vec) {
                cout << val << " ";
            }
            cout << endl;
        }
        return dp[prices.size() - 1][1];
    }
};

123.买卖股票的最佳时机

题目链接 文章讲解 视频讲解

动规五部曲：

• dp数组含义：
  • dp[j][0]: 不做任何操作
  • dp[j][1]: 第一次持有股票的最大现金
  • dp[j][2]: 第一次不持有股票
  • dp[j][3]: 第二次持有股票
  • dp[j][4]: 第二次不持有股票
• 递推公式：
  • dp[j][0] = dp[j-1][0]; 不做任何操作手中的现金始终为0
  • dp[j][1] = max(dp[j-1][1], dp[j-1][0] - prices[j]);
  • dp[j][2] = max(dp[j-1][2], dp[j-1][1] + prices[j]);
  • dp[j][3] = max(dp[j-1][3], dp[j-1][2] - prices[j]);
  • dp[j][4] = max(dp[j-1][4], dp[j-1][3] + prices[j]);
• 初始化：
  • dp[0][0] = 0;
  • dp[0][1] = -prices[0];
  • dp[0][2] = 0; // 第一天买入第一天卖出；
  • dp[0][3] = -prices[0]; // 第一天卖出之后再买入
  • dp[0][4] = 0; // 再次买入后再次卖出
• 遍历顺序：从小到大遍历
• 打印dp数组

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(5));

        dp[0][0] = 0;
        dp[0][1] = -prices[0]; // 第一次持有
        dp[0][2] = 0; // 第一次不持有
        dp[0][3] = -prices[0]; // 第二次持有
        dp[0][4] = 0; // 第二次不持有

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

        // return max(dp[0][0], dp[prices.size() - 1][4]);
        return dp[prices.size() - 1][4];
    }
};