买卖股票问题通用解法

思路

leetcode上买卖股票系列问题：

• 121. Best Time to Buy and Sell Stock 只能买卖一次
• 122. Best Time to Buy and Sell Stock II 能买卖无数次
• 123. Best Time to Buy and Sell Stock III 至多买卖2次
• 188. Best Time to Buy and Sell Stock IV 至多买卖k次
• 309. Best Time to Buy and Sell Stock with Cooldown 能买卖无数次，但有冷静期
• 714. Best Time to Buy and Sell Stock with Transaction Fe
  e 能买卖无数次，但是每次交易有手续费

大体思路都是DP，用通用解法能暴力过121、122、123，稍加修改能过309。

188用通用解法会提示runtime error，需要进行状态压缩，解法可以参考这个;

通用解法

var maxProfit = function (maxTransTimes, prices) {
  if (!maxTransTimes || !prices || !prices.length) {
    return 0;
  }

  const helper = function (prices, maxTransTimes) {
    //三维数组mp[i][k][j]
    //i标识第几天（0<=i<=prices.length-1）
    //k标识到第i天进行了多少笔交易（0<=k<=maxTransTimes），注意买入后并卖出才算一笔完整的交易
    //j标识第i天手上有没有股票（0<=j<=1）
    const mp = new Array(prices.length).fill(0).map((v) => {
      return new Array(maxTransTimes + 1).fill(0).map((v) => {
        return [0, 0];
      });
    });

    for (let k = 0; k <= maxTransTimes; k++) {
      if (k === 0) {
        mp[0][k][1] = -prices[0]; //第1天买入
      } else {
        //第1天是无法完成交易的
        mp[0][k][0] = -Infinity;
        mp[0][k][1] = -Infinity;
      }
    }

    for (let i = 1; i < prices.length; i++) {
      for (let k = 0; k <= maxTransTimes; k++) {
        mp[i][k][0] = Math.max(
          mp[i - 1][k][0], //第i天不动
          k === 0 ? -Infinity : mp[i - 1][k - 1][1] + prices[i] //第i天卖
        );
        mp[i][k][1] = Math.max(
          mp[i - 1][k][1], //第i天不动
          mp[i - 1][k][0] - prices[i] //第i天买
        );
      }
    }

    return mp;
  };

  const mp = helper(prices, maxTransTimes);
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let k = 0; k <= maxTransTimes; k++) {
      max = Math.max(max, mp[i][k][0]);
    }
  }

  return max;
};