leetcode 刷题 log day 50（继续股票专题

• 123. 买卖股票的最佳时机III
  【思路】这次的难点在于限定了买卖的次数，只能买卖两次，那么就会有五种情况：
  1. 不操作：dp[i][0] = dp[i - 1]
  2. 第一次买入：dp[i][1] = dp[i - 1][0] - prices[i]
  3. 第一次卖出：dp[i][2] = p[i - 1][1] + prices[i]
  4. 第二次买入：dp[i][3] = dp[i - 1][2] - pricers[i]
  5. 第二次卖出：dp[i][4] = dp[i - 1][3] + prices[i]

  var maxProfit = function(prices) {
    const dp = new Array(prices.length).fill([0, 0, 0, 0, 0]);
    dp[0] = [0, -prices[0], 0, -prices[0], 0];
  
    for (let i = 1; i < prices.length; i++) {
      dp[i][0] = dp[i - 1][0];  // 不操作
      dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);  // 第一次买入
      dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);  // 第一次卖出
      dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);  // 第二次买入
      dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);  // 第二次卖出
    }
    return dp[prices.length - 1][4];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

• 188. 买卖股票的最佳时机IV
  【思路】这道题比上道题的难点在于不是两次，而是 k 次，但我们根据上一道题的经验罗列可能出现的情况，会发现奇数是买进，偶数是卖出。

  var maxProfit = function(k, prices) {
    let dp = new Array(2 * k + 1).fill(0);
  
    // 初始化买入状态（奇数）
    for(let i = 1; i <= 2 * k; i += 2) {
      dp[i] = -prices[0];
    }
  
    for(let i = 1; i < prices.length; i++) {
      for (let j = 1; j <= 2 * k; j++) {
        // j 为奇数考虑买入状态
        if (j % 2) {
          dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
        } else {
          // 偶数考虑卖出
          dp[j] = Math.max(dp[j], dp[j - 1] + prices[i]);
        }
      }
    }
    console.log(dp)
    return dp[2 * k];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22

参考代码随想录：https://www.programmercarl.com/