309. 最佳买卖股票时机含冷冻期（JS实现）

客官°小女子只卖身不卖艺 2022-11-27 15:59 128阅读 0赞

## 1 题目 ##

> 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。  
> 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:  
> 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。  
> 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。  
> 示例:  
> 输入: \[1,2,3,0,2\]  
> 输出: 3  
> 解释: 对应的交易状态为: \[买入, 卖出, 冷冻期, 买入, 卖出\]

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

## 2 思路 ##

**这道题是股票系列的变种, 动态规划`d[i][j]`，代表第`i`天持有状态为`j`的最大利润，状态转移方程`d[i][0] = Math.max(d[i-1][0], d[i-1][1] + prices[i])`、`d[i][1] = Math.max(d[i-1][1], d[i-2][0] - prices[i])`，注意由于股票有冷冻期，因此只能买入第`i-2`天的股票**

## 3代码 ##

/** * @param {number[]} prices * @return {number} */
    var maxProfit = function(prices) { 
        if (prices.length === 0) return 0;
        const d = [];
        const min = Number.MIN_SAFE_INTEGER;
    
        for (let i=0; i<prices.length; i++) { 
            if (!d[i]) d[i] = [];
            d[i][0] = 0;
            d[i][1] = 0;
        }
    
        for (let i=0; i<prices.length; i++) { 
            if (i === 0) {    //第一天特殊处理
                d[0][0] = 0;
                d[0][1] = -prices[i];
                continue;
            }
            if (i === 1) {   //第二天情况特殊处理
                d[i][0] = Math.max(d[i-1][0], d[i-1][1] + prices[i]);
                d[i][1] = Math.max(d[i-1][1], -prices[i]);
                continue;
            }
            d[i][0] = Math.max(d[i-1][0], d[i-1][1] + prices[i]);
            d[i][1] = Math.max(d[i-1][1], d[i-2][0] - prices[i]);
        }
    
        return d[prices.length-1][0];
    
    
    };