系列題目：
- Leetcode 121.買賣股票的最佳時(shí)機(jī)1 【只能交易1次】
- Leetcode 122.買賣股票的最佳時(shí)機(jī)2 【可以無(wú)數(shù)次交易】
- Leetcode 123.買賣股票的最佳時(shí)機(jī)3 【只能交易2次】
- Leetcode 188.買賣股票的最佳時(shí)機(jī)4 【可以交易k次】
- Leetcode 714.買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi) 【含手續(xù)費(fèi)】
- Leetcode 309.買賣股票的最佳時(shí)機(jī)含冷凍期 【含冷凍期】
特點(diǎn)： 要獲得最大利益， 有交易次數(shù)約束， 交易手續(xù)費(fèi)、 冷凍期
核心思想：
每天的狀態(tài)可以有： 賣出股票 、 買入股票 、 什么也不做
所以每天的利潤(rùn)，可以這樣表示
profit_sell = Math.max(什么也不做，由前一個(gè)狀態(tài)轉(zhuǎn)換今日賣出的利潤(rùn) )
profit_buy = Math.max(什么也不做，由前一個(gè)狀態(tài)轉(zhuǎn)換今日買入的利潤(rùn) )
用代碼表示動(dòng)態(tài)轉(zhuǎn)換過(guò)程：
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]
具體題目代碼
-
買賣股票的最佳時(shí)機(jī) 【只能交易1次】
關(guān)鍵： 只能交易一次， 所以買入的最大利益更新 是: 0 - prices[i];
這里和多次買賣不同， 因?yàn)槎啻钨I賣的買入利益從前一個(gè)賣出利益更新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 }
-
買賣股票的最佳時(shí)機(jī)2 【可以無(wú)數(shù)次交易】
每天更新兩種狀態(tà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, profit_sell-prices[i]) } return profit_sell };
-
買賣股票的最佳時(shí)機(jī)3 【只能交易2次】
每天有四種狀態(tài)： 第1次買入 / 第1次賣出 / 第2次買入 / 第2次賣出
轉(zhuǎn)換： 第2次買入的交易利益由第一次賣出轉(zhuǎn)換而來(lái)var maxProfit = function(prices) { // 初始化 let in_1 = 0 - prices[0] // 第1次買入的利潤(rùn) 初始化 let out_1 = 0 // 第1次賣出利潤(rùn) 初始化 let in_2 = -prices[0] let out_2 = 0 // 狀態(tài)轉(zhuǎn)換過(guò)程 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 };
-
買賣股票的最佳時(shí)機(jī)4 【可以交易k次】
關(guān)鍵： 可以交易k次， 是在上題的擴(kuò)展。 每一天都要給2k個(gè)狀態(tài)賦值，所以多了1層循環(huán)。 其余的和上題的一樣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] } } // 真正動(dòng)態(tài)規(guī)劃，賦值 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 };
-
買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi) 【含手續(xù)費(fèi)】
和買賣股票問(wèn)題2是一樣的無(wú)限次數(shù)
關(guān)鍵： 在每次賣出的利潤(rùn) - 手續(xù)費(fèi)var maxProfit = function(prices, fee) { // 初始化 let profit_sell = 0 let profit_buy = -prices[0] //動(dòng)態(tài)轉(zhuǎn)換過(guò)程 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 }
-
買賣股票的最佳時(shí)機(jī)含冷凍期 【含冷凍期】
關(guān)鍵點(diǎn)： 用一個(gè)變量記住冷凍期時(shí)的利益， 冷凍期就是記住前一次賣出的最大利益
轉(zhuǎn)換： 買入的最大利益 需要 從冷凍期轉(zhuǎn)換過(guò)來(lái)var maxProfit = function(prices) { // 初始化 let profit_sell = 0 let profit_buy = -prices[0] let profit_freeze = 0 // 冷凍期利潤(rùn) // 動(dòng)態(tài)轉(zhuǎn)換過(guò)程 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 // 冷凍期利潤(rùn)其實(shí)是前一天賣出的利潤(rùn)的記憶 } return profit_sell };
