309_javascript.js

// 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

// 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
// 示例:

// 输入: [1,2,3,0,2]
// 输出: 3
// 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

// 动态规划

// 因为当天卖出股票实际上也是属于“不持有”的状态，那么第i天如果不持有，那这个“不持有”就有了两种状态：1.本来就不持有，指不是因为当天卖出了才不持有的；2.第i天因为卖出了股票才变得不持有

// 而持有股票依旧只有一种状态

// 所以对于每一天i，都有可能是三种状态：
// 0.不持股且当天没卖出,定义其最大收益dp[i][0];
// 1.持股,定义其最大收益dp[i][1]；
// 2.不持股且当天卖出了，定义其最大收益dp[i][2]；

// 初始化：
// dp[0][0]=0;//本来就不持有，啥也没干
// dp[0][1]=-1*prices[0];//第0天只买入
// dp[0][2]=0;//可以理解成第0天买入又卖出，那么第0天就是“不持股且当天卖出了”这个状态了，其收益为0，所以初始化为0是合理的

// 重头戏：

// 一、第i天不持股且没卖出的状态dp[i][0]，也就是我没有股票，而且还不是因为我卖了它才没有的，那换句话说是从i-1天到第i天转移时，它压根就没给我股票！所以i-1天一定也是不持有，那就是不持有的两种可能：i-1天不持股且当天没有卖出dp[i-1][0]；i-1天不持股但是当天卖出去了dp[i-1][2]；
// 所以： dp[i][0]=max(dp[i-1][0],dp[i-1][2])

// 二、第i天持股dp[i][1]，今天我持股，来自两种可能：
// 1、要么是昨天我就持股，今天继承昨天的，也就是dp[i-1][1]，这种可能很好理解；
// 2、要么：是昨天我不持股，今天我买入的，但前提是昨天我一定没卖！因为如果昨天我卖了，那么今天我不能交易！也就是题目中所谓“冷冻期”的含义，只有昨天是“不持股且当天没卖出”这个状态，我今天才能买入！所以是dp[i-1][0]-p[i]
// 所以： dp[i][1]=max(dp[i-1][1],dp[i-1][0]-p[i])

// 三、i天不持股且当天卖出了，这种就简单了，那就是说昨天我一定是持股的，要不然我今天拿什么卖啊，而持股只有一种状态，昨天持股的收益加上今天卖出得到的新收益，就是dp[i-1][1]+p[i]啦
// 所以：dp[i][2]=dp[i-1][1]+p[i]

// 总结：最后一天的最大收益有两种可能，而且一定是“不持有”状态下的两种可能，把这两种“不持有”比较一下大小，返回即可

/**
 * @param {number[]} prices
 * @return {number}
 */
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let dp = Array.from(new Array(prices.length), (arr) => new Array(3));

  dp[0][0] = 0;
  // 当天持有 即买入
  dp[0][1] = -prices[0];
  // 可以理解为当天买入卖出
  dp[0][2] = 0;
  for (let i = 1; i < prices.length; i++) {
    // 设三种状态 持有 卖出 和冷却期
    // 当天不持有没卖出 1 冷却期 2 当天卖出
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
    // 当天持有 1 前一天也持有今天没卖 2 今天刚买入
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    // 当天不持有卖出 1 前一天持有
    dp[i][2] = dp[i - 1][1] + prices[i];
    console.log(dp[i][0], dp[i][1], dp[i][2]);
  }
  return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][0]);
};