Leetcode - 买卖股票最佳时机

系列题目：

1. Leetcode 121.买卖股票的最佳时机1 【只能交易1次】
2. Leetcode 122.买卖股票的最佳时机2 【可以无数次交易】
3. Leetcode 123.买卖股票的最佳时机3 【只能交易2次】
4. Leetcode 188.买卖股票的最佳时机4 【可以交易k次】
5. Leetcode 714.买卖股票的最佳时机含手续费 【含手续费】
6. Leetcode 309.买卖股票的最佳时机含冷冻期 【含冷冻期】

特点： 要获得最大利益， 有交易次数约束， 交易手续费、 冷冻期

核心思想：

每天的状态可以有： 卖出股票 、 买入股票 、 什么也不做

屏幕快照 2020-03-01 15.01.14.png

所以每天的利润，可以这样表示
profit_sell = Math.max(什么也不做，由前一个状态转换今日卖出的利润 )
profit_buy = Math.max(什么也不做，由前一个状态转换今日买入的利润 )

用代码表示动态转换过程：

for(let i=0; i<n; i++){
  profit_sell = Math.max(profit_out, profit_in + prices[i])
  profit_buy = Math.max(profit_buy, profit_sell-prices[i])
}

初始化

profit_sell = 0
profit_buy = - prices[0]

具体题目代码

1. 买卖股票的最佳时机 【只能交易1次】
   关键： 只能交易一次， 所以买入的最大利益更新 是: 0 - prices[i];
   这里和多次买卖不同， 因为多次买卖的买入利益从前一个卖出利益更新

   var maxProfit = function(prices) {
       let profit_sell = 0
       let profit_buy = -prices[0]
   
       for(let i=0; i< prices.length; i++){
           profit_sell = Math.max(profit_sell, profit_buy + prices[i])
           profit_buy = Math.max(profit_buy, -prices[i])
       }
       
       return  profit_sell
   }
   

2. 买卖股票的最佳时机2 【可以无数次交易】

   每天更新两种状态的最大利益

   var maxProfit = function(prices) {
       let profit_sell = 0
       let profit_buy = - prices[0]
   
       for(let i=0; i<prices.length; i++){
           profit_sell = Math.max(profit_sell, profit_buy + prices[i])
           profit_buy = Math.max(profit_buy, profit_sell-prices[i])
       }
   
       return profit_sell
   };
   

3. 买卖股票的最佳时机3 【只能交易2次】
   每天有四种状态： 第1次买入 / 第1次卖出 / 第2次买入 / 第2次卖出
   转换： 第2次买入的交易利益由第一次卖出转换而来

   var maxProfit = function(prices) {
       // 初始化
       let in_1 = 0 - prices[0]    // 第1次买入的利润 初始化
       let out_1 = 0               // 第1次卖出利润 初始化
       let in_2 = -prices[0]
       let out_2 = 0 
   
       // 状态转换过程
       let len = prices.length
       for(let i=0; i<len; i++){
           out_2 = Math.max(out_2, in_2 + prices[i])
           in_2 = Math.max(in_2, out_1 - prices[i])
           out_1 = Math.max(out_1, in_1 + prices[i])
           in_1 = Math.max(in_1, -prices[i])
       }
   
       return out_2
   };
   

4. 买卖股票的最佳时机4 【可以交易k次】
   关键： 可以交易k次， 是在上题的扩展。 每一天都要给2k个状态赋值，所以多了1层循环。 其余的和上题的一样

   ar maxProfit = function(k, prices) {
   
       let n = prices.length;
       if (k > n / 2) {
           k = Math.floor(n/2)  
       }
   
       // 初始化
       let profit = []
       for(let i=0; i<=k; i++){
           profit[i] = {
               sell : 0,
               buy: -prices[0]
           }
       }
   
       // 真正动态规划，赋值
       for(let i=0; i<prices.length; i++){
           for(let j=1; j<=k; j++){
              profit[j] = {
                  sell: Math.max(profit[j].sell, profit[j].buy + prices[i]),
                  buy: Math.max(profit[j].buy, profit[j-1].sell - prices[i])
              }
           }
       }
   
       return profit[k].sell
   };
   

5. 买卖股票的最佳时机含手续费 【含手续费】
   和买卖股票问题2是一样的无限次数
   关键： 在每次卖出的利润 - 手续费

   var maxProfit = function(prices, fee) {
       // 初始化
       let profit_sell = 0
       let profit_buy = -prices[0]
   
       //动态转换过程
       for(let i=0; i<prices.length; i++){
           profit_sell = Math.max(profit_sell, profit_buy + prices[i] - fee)
           profit_buy = Math.max(profit_buy, profit_sell - prices[i])
       }
   
       return profit_sell
   }
   

6. 买卖股票的最佳时机含冷冻期 【含冷冻期】
   关键点： 用一个变量记住冷冻期时的利益， 冷冻期就是记住前一次卖出的最大利益
   转换： 买入的最大利益 需要 从冷冻期转换过来

   var maxProfit = function(prices) {
       // 初始化
       let profit_sell = 0
       let profit_buy = -prices[0]
       let profit_freeze = 0  // 冷冻期利润
   
       // 动态转换过程    
       for(let i=0; i<prices.length; i++){
           let temp = profit_sell
           profit_sell = Math.max(profit_sell, profit_buy + prices[i])
           profit_buy = Math.max(profit_buy, profit_freeze - prices[i])
           profit_freeze = temp   // 冷冻期利润其实是前一天卖出的利润的记忆
       }
       return profit_sell
   };