第九章 動(dòng)態(tài)規(guī)劃part09
188.買賣股票的最佳時(shí)機(jī)IV
本題是123.買賣股票的最佳時(shí)機(jī)III 的進(jìn)階版
文章講解
思路
- 確定dp數(shù)組以及下標(biāo)的含義
在動(dòng)態(tài)規(guī)劃：123.買賣股票的最佳時(shí)機(jī)III (opens new window)中
睁搭，使用二維數(shù)組 dp[i][j] ：第i天的狀態(tài)為j赶诊，所剩下的最大現(xiàn)金是dp[i][j]，實(shí)際上除了0以外园骆，j的狀態(tài)表示偶數(shù)就是賣出舔痪，奇數(shù)就是買入。本題也可以用二維數(shù)組表示锌唾，題目要求是至多有K筆交易锄码，那么j的范圍就定義為 2 * k + 1 就可以了。只是奇數(shù)代表買入鸠珠，偶數(shù)代表賣出巍耗。 - 確定遞推公式
-
達(dá)到dp[i][1]狀態(tài)，有兩個(gè)具體操作：
- 操作一：第i天買入股票了渐排，那么dp[i][1] = dp[i - 1][0] - prices[i]
- 操作二：第i天沒有操作炬太，而是沿用前一天買入的狀態(tài)，即：dp[i][1] = dp[i - 1][1]
- 選最大的驯耻，所以
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]); -
同理dp[i][2]也有兩個(gè)操作：
- 操作一：第i天賣出股票了亲族，那么dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二：第i天沒有操作，沿用前一天賣出股票的狀態(tài)可缚，即：dp[i][2] = dp[i - 1][2]
- 所以
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]) - 同理可以類比剩下的狀態(tài)霎迫，代碼如下：
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
最大的區(qū)別就是這里要類比j為奇數(shù)是買，偶數(shù)是賣的狀態(tài)帘靡。
- dp數(shù)組如何初始化
- 第0天沒有操作知给，這個(gè)最容易想到，就是0描姚，即：dp[0][0] = 0;
- 第0天做第一次買入的操作涩赢，dp[0][1] = -prices[0];
- 第0天做第一次賣出的操作，可以理解為當(dāng)天買入轩勘，當(dāng)天賣出筒扒，所以dp[0][2] = 0;
- 第0天第二次買入操作：第二次買入依賴于第一次賣出的狀態(tài)，其實(shí)相當(dāng)于第0天第一次買入了绊寻，第一次賣出了花墩，然后在買入一次（第二次買入），那么現(xiàn)在手頭上沒有現(xiàn)金澄步，只要買入冰蘑，現(xiàn)金就做相應(yīng)的減少。
所以第二次買入操作驮俗，初始化為：dp[0][3] = -prices[0]; - 第二次賣出初始化dp[0][4] = 0;
所以同理可以推出dp[0][j]當(dāng)j為奇數(shù)的時(shí)候都初始化為 -prices[0]
以此分別類比奇偶天數(shù)的狀態(tài)
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
確定遍歷順序
從遞歸公式其實(shí)已經(jīng)可以看出懂缕，一定是從前向后遍歷，因?yàn)閐p[i]王凑，依靠dp[i - 1]的數(shù)值搪柑。-
舉例推導(dǎo)dp數(shù)組
以輸入[1,2,3,4,5]，k=2為例索烹。
image.png
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length == 0) return 0;
int len = prices.length;
// [天數(shù)][股票狀態(tài)]
// 股票狀態(tài): 奇數(shù)表示第 k 次交易持有, 偶數(shù)表示第 k 次交易不持有, 0 表示沒有操作
int[][] dp = new int[len][2 * k + 1];
for(int i = 1; i < k * 2; i += 2){
dp[0][i] = - prices[0];
}
for(int i = 1; i < len; i++){
for(int j = 0; j <= 2 * k - 1; j += 2){
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[len - 1][k * 2];
}
}
- 為什么在 for (int j = 0; j < k*2 - 1; j += 2) 中工碾， j < k*2 - 1
在for (int j = 0; j < k*2 - 1; j += 2)循環(huán)中，j的上限是k*2 - 1
假設(shè)k是允許的最大交易次數(shù)： -
k * 2是我們需要考慮的所有狀態(tài)的總數(shù)百姓，因?yàn)槊看谓灰装I入和賣出兩個(gè)狀態(tài)渊额。 -
k * 2 - 1是j的最大有效值，因?yàn)?j達(dá)到k * 2時(shí)已經(jīng)是一個(gè)完整交易的結(jié)束狀態(tài)垒拢。
在 for 循環(huán)中：
-
j的起點(diǎn)是0旬迹，這表示沒有進(jìn)行任何操作的狀態(tài)。 -
j每次增加2求类，確保我們只在需要更新交易狀態(tài)的位置進(jìn)行操作（即處理買入或賣出的狀態(tài)）奔垦。
具體解釋代碼中的循環(huán)：
for (int j = 0; j < k*2 - 1; j += 2) {
// 更新買入狀態(tài): 第 j / 2 + 1 次交易買入的最大利潤(rùn)
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
// 更新賣出狀態(tài): 第 j / 2 + 1 次交易賣出的最大利潤(rùn)
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
-
j + 1更新的是買入狀態(tài)。 -
j + 2更新的是賣出狀態(tài)尸疆。
由于 j 的最大值為 k * 2 - 1椿猎，所以 j + 1 的最大值為 k * 2 - 1（代表第 k 次交易的買入狀態(tài)），而 j + 2 的最大值為 k * 2（代表第 k 次交易的賣出狀態(tài)）寿弱。
這就是為什么 for 循環(huán)中的 j 條件是 j < k * 2 - 1 的原因犯眠。
309.最佳買賣股票時(shí)機(jī)含冷凍期
本題加了一個(gè)冷凍期，狀態(tài)就多了症革，有點(diǎn)難度筐咧，大家要把各個(gè)狀態(tài)分清，思路才能清晰
文章講解
思路
具體可以區(qū)分出如下四個(gè)狀態(tài)：
- 狀態(tài)一：持有股票狀態(tài)（今天買入股票噪矛，或者是之前就買入了股票然后沒有操作量蕊，一直持有）
- 不持有股票狀態(tài)，這里就有兩種賣出股票狀態(tài)
- 狀態(tài)二：保持賣出股票的狀態(tài)（兩天前就賣出了股票摩疑，度過一天冷凍期危融。或者是前一天就是賣出股票狀態(tài)雷袋，一直沒操作）
- 狀態(tài)三：今天賣出股票
- 狀態(tài)四：今天為冷凍期狀態(tài)吉殃，但冷凍期狀態(tài)不可持續(xù)，只有一天楷怒！
確定dp數(shù)組以及下標(biāo)的含義
dp[i][j]蛋勺，第i天狀態(tài)為j，所剩的最多現(xiàn)金為dp[i][j]鸠删。確定遞推公式
達(dá)到買入股票狀態(tài)（狀態(tài)一）即：dp[i][0]抱完，有兩個(gè)具體操作：
- 操作一：前一天就是持有股票狀態(tài)（狀態(tài)一），dp[i][0] = dp[i - 1][0]
- 操作二：今天買入了刃泡，有兩種情況
- 前一天是冷凍期（狀態(tài)四）巧娱，dp[i - 1][3] - prices[i]
- 前一天是保持賣出股票的狀態(tài)（狀態(tài)二）碉怔，dp[i - 1][1] - prices[i]
那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);
達(dá)到保持賣出股票狀態(tài)（狀態(tài)二）即：dp[i][1]，有兩個(gè)具體操作：
- 操作一：前一天就是狀態(tài)二
- 操作二：前一天是冷凍期（狀態(tài)四）
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
達(dá)到今天就賣出股票狀態(tài)（狀態(tài)三）禁添，即：dp[i][2] 撮胧，只有一個(gè)操作：
- 昨天一定是持有股票狀態(tài)（狀態(tài)一），今天賣出
即：dp[i][2] = dp[i - 1][0] + prices[i];
達(dá)到冷凍期狀態(tài)（狀態(tài)四）老翘，即：dp[i][3]芹啥，只有一個(gè)操作：
- 昨天賣出了股票（狀態(tài)三）
dp[i][3] = dp[i - 1][2];
綜上分析，遞推代碼如下：
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i-1][1] - prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);
dp[i][2] = Math.max(dp[i-1][0] + prices[i]);
dp[i][3] = dp[i-1][2];
- dp數(shù)組如何初始化
這里主要討論一下第0天如何初始化铺峭。
如果是持有股票狀態(tài)（狀態(tài)一）那么：dp[0][0] = -prices[0]墓怀，一定是當(dāng)天買入股票。
保持賣出股票狀態(tài)（狀態(tài)二）卫键，這里其實(shí)從 「狀態(tài)二」的定義來說 傀履，很難明確應(yīng)該初始多少，這種情況我們就看遞推公式需要我們給他初始成什么數(shù)值永罚。
如果i為1啤呼，第1天買入股票，那么遞歸公式中需要計(jì)算 dp[i - 1][1] - prices[i] 呢袱，即 dp[0][1] - prices[1]官扣，那么大家感受一下 dp[0][1] （即第0天的狀態(tài)二）應(yīng)該初始成多少，只能初始為0羞福。想一想如果初始為其他數(shù)值惕蹄，是我們第1天買入股票后 手里還剩的現(xiàn)金數(shù)量是不是就不對(duì)了。
今天賣出了股票（狀態(tài)三）治专，同上分析卖陵，dp[0][2]初始化為0，dp[0][3]也初始為0张峰。
確定遍歷順序
從遞歸公式上可以看出泪蔫，dp[i] 依賴于 dp[i-1]，所以是從前向后遍歷喘批。-
舉例推導(dǎo)dp數(shù)組
以 [1,2,3,0,2] 為例撩荣，dp數(shù)組如下：
image.png
class Solution {
public int maxProfit(int[] prices) {
if(prices == null) return 0;
int len = prices.length;
int[][] dp = new int[len][4];
/**
1. [i][0] holding the stock
2. [i][1] after cooldown but stil not buing the stock
3. [i][2] selling the stock
4. [i][3] cooldown
*/
dp[0][0] = -prices[0];
for(int i = 1; i < len; i++){
dp[i][0] = Math.max(Math.max(dp[i-1][0], dp[i-1][3] - prices[i]), dp[i-1][1] - prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);
dp[i][2] = dp[i-1][0] + prices[i];
dp[i][3] = dp[i-1][2];
}
return Math.max(dp[len-1][3], Math.max(dp[len-1][1], dp[len-1][2]));
}
}
714.買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)
相對(duì)122.買賣股票的最佳時(shí)機(jī)II ，本題只需要在計(jì)算賣出操作的時(shí)候減去手續(xù)費(fèi)就可以了饶深，代碼幾乎是一樣的餐曹，可以嘗試自己做一做。
文章講解
思路
相對(duì)于 122.買賣股票的最佳時(shí)機(jī)II敌厘，本題只需要在計(jì)算賣出操作的時(shí)候減去手續(xù)費(fèi)就可以了台猴，代碼幾乎是一樣的。
唯一差別在于遞推公式
- dp數(shù)組的含義：
dp[i][0] 表示第i天持有股票所省最多現(xiàn)金。 dp[i][1] 表示第i天不持有股票所得最多現(xiàn)金
如果第i天持有股票即dp[i][0]饱狂， 那么可以由兩個(gè)狀態(tài)推出來
- 第i-1天就持有股票曹步，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：dp[i - 1][0]
- 第i天買入股票嗡官，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金減去 今天的股票價(jià)格 即：dp[i - 1][1] - prices[i]
所以：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
如果第i天不持有股票即dp[i][1]的情況箭窜， 依然可以由兩個(gè)狀態(tài)推出來
- 第i-1天就不持有股票毯焕，那么就保持現(xiàn)狀衍腥，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：dp[i - 1][1]
- 第i天賣出股票，所得現(xiàn)金就是按照今天股票價(jià)格賣出后所得現(xiàn)金纳猫，注意這里需要有手續(xù)費(fèi)了即：dp[i - 1][0] + prices[i] - fee
所以：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
class Solution {
public int maxProfit(int[] prices, int fee) {
int[] dp = new int[2];
// 0代表持有婆咸，1代表賣出
dp[0] = -prices[0];
dp[1] = 0;
for(int i = 1; i <= prices.length; i++){
//因?yàn)檠h(huán)是從1到len，所以實(shí)際上i=1芜辕，訪問的是prices[0],所以為了保證數(shù)組索引對(duì)齊尚骄，這里面都是prices[i-1]
//區(qū)別于二維數(shù)組的解法，因?yàn)槎S數(shù)組的循環(huán)是從1到len-1侵续，使用i訪問prices[i]
//第i-1天（這時(shí)候是用dp[0]保存的）就持有; 或第i天買入股票倔丈，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金減去 今天的股票價(jià)格
dp[0] = Math.max(dp[0], dp[1] - prices[i - 1]);
//第i-1天就不持有；或第i天賣出股票状蜗，所得現(xiàn)金就是按照今天股票價(jià)格賣出再減去手續(xù)費(fèi)后所得現(xiàn)金
dp[1] = Math.max(dp[1], dp[0] + prices[i - 1] - fee);
}
return dp[1]; //二維數(shù)組應(yīng)該返回length-1需五，但是這里改了for循環(huán)里 i <= prices.length
}
}
股票總結(jié)
股票問題做一個(gè)總結(jié)吧
