2023年10月26日 - 动态规划10

121. 买卖股票的最佳时机

dp[i][0]代表第i天不持有股票

dp[i][1]代表第i天持有股票

 class Solution {
 public:
     int maxProfit(vector<int>& prices) {
         int len = prices.size();
         if (len == 0) return 0;
         vector<vector<int>> dp(len, vector<int>(2));
         dp[0][0] = 0;
         dp[0][1] = -prices[0];
         for (int i = 1; i < len; i++) {
             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] +  prices[i]);
             dp[i][1] = max(dp[i - 1][1], -prices[i]);
         }
         return dp[len - 1][0];  //最后一天不持有股票肯定比持有股票手头的钱多
     }
 };

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

区别在于第i天持有股票时，可能是第i - 1不持有，但是之前也可能买卖多次，所以 dp[i - 1][0] - prices[i]，代表第i天才买入，但是目前钱不是0而是dp[i - 1][0]

 class Solution {
 public:
     int maxProfit(vector<int>& prices) {
         int len = prices.size();
         if (len == 0) return 0;
         vector<vector<int>> dp(len, vector<int>(2));
         dp[0][0] = 0;
         dp[0][1] = -prices[0];
         for (int i = 1; i < len; 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[len - 1][0];  //最后一天不持有股票肯定比持有股票手头的钱多
     }
 };