系列题目:
- Leetcode 121.买卖股票的最佳时机1 【只能交易1次】
- Leetcode 122.买卖股票的最佳时机2 【可以无数次交易】
- Leetcode 123.买卖股票的最佳时机3 【只能交易2次】
- Leetcode 188.买卖股票的最佳时机4 【可以交易k次】
- Leetcode 714.买卖股票的最佳时机含手续费 【含手续费】
- 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次】
关键: 只能交易一次, 所以买入的最大利益更新 是: 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 【可以无数次交易】
每天更新两种状态的最大利益
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 【只能交易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 【可以交易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 };
-
买卖股票的最佳时机含手续费 【含手续费】
和买卖股票问题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 }
-
买卖股票的最佳时机含冷冻期 【含冷冻期】
关键点: 用一个变量记住冷冻期时的利益, 冷冻期就是记住前一次卖出的最大利益
转换: 买入的最大利益 需要 从冷冻期转换过来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 };