第九章 動態(tài)規(guī)劃part08
121. 買賣股票的最佳時機
思路
- 貪心的解法：
class Solution {
public int maxProfit(int[] prices) {
// 找到一個最小的購入點
int low = Integer.MAX_VALUE;
// res不斷更新，直到數(shù)組循環(huán)完畢
int res = 0;
for(int i = 0; i < prices.length; i++){
low = Math.min(prices[i], low);
res = Math.max(prices[i] - low, res);
}
return res;
}
}
- 動態(tài)規(guī)劃
確定dp數(shù)組（dp table）以及下標的含義
dp[i][0] 表示第i天持有股票所得最多現(xiàn)金 格嘁，dp[i][1] 表示第i天不持有股票所得最多現(xiàn)金-
確定遞推公式
如果第i天持有股票即dp[i][0]， 那么可以由兩個狀態(tài)推出來- 第i-1天就持有股票廊移，那么就保持現(xiàn)狀糕簿，所得現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：dp[i - 1][0]
- 第i天買入股票，所得現(xiàn)金就是買入今天的股票后所得現(xiàn)金即：-prices[i]
- 那么dp[i][0]應該選所得現(xiàn)金最大的狡孔，所以
dp[i][0] = max(dp[i - 1][0], -prices[i]);
如果第i天不持有股票即dp[i][1]懂诗， 也可以由兩個狀態(tài)推出來
- 第i-1天就不持有股票，那么就保持現(xiàn)狀苗膝，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：dp[i - 1][1]
- 第i天賣出股票殃恒，所得現(xiàn)金就是按照今天股票價格賣出后所得現(xiàn)金即：prices[i] + dp[i - 1][0]
- 同樣dp[i][1]取最大的，
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
dp數(shù)組如何初始化
由遞推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出其基礎(chǔ)都是要從dp[0][0]和dp[0][1]推導出來辱揭。
那么dp[0][0]表示第0天持有股票离唐，此時的持有股票就一定是買入股票了，因為不可能有前一天推出來问窃，所以dp[0][0] -= prices[0];
dp[0][1]表示第0天不持有股票亥鬓，不持有股票那么現(xiàn)金就是0，所以dp[0][1] = 0;確定遍歷順序
從遞推公式可以看出dp[i]都是由dp[i - 1]推導出來的域庇，那么一定是從前向后遍歷嵌戈。-
舉例推導dp數(shù)組
以示例1，輸入：[7,1,5,3,6,4]為例听皿，dp數(shù)組狀態(tài)如下：
image.png
class Solution {
public int maxProfit(int[] prices) {
//版本1
int len = prices.length;
if(prices == null || len == 0) return 0;
// dp[i][0]代表第i天持有股票的最大收益
// dp[i][1]代表第i天不持有股票的最大收益
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < len; i++){
dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
}
return dp[len-1][1];
}
}
從遞推公式可以看出熟呛，dp[i]只是依賴于dp[i - 1]的狀態(tài)。
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
那么我們只需要記錄 當前天的dp狀態(tài)和前一天的dp狀態(tài)就可以了尉姨，可以使用滾動數(shù)組來節(jié)省空間
i % 2 的作用是用來在 dp 數(shù)組的兩行之間切換庵朝，使得我們能夠復用數(shù)組空間。例如：
- 當
i為偶數(shù)時，i % 2為 0偿短，表示使用dp數(shù)組的第 0 行來存儲第i天的狀態(tài)欣孤。 - 當
i為奇數(shù)時，i % 2為 1昔逗，表示使用dp數(shù)組的第 1 行來存儲第i天的狀態(tài)降传。
這樣，我們就可以使用 dp[0] 和 dp[1] 兩行來分別存儲當前和前一天的狀態(tài)勾怒，達到節(jié)省空間的目的婆排。
class Solution {
public int maxProfit(int[] prices) {
//版本1
int len = prices.length;
if(prices == null || len == 0) return 0;
// dp[i][0]代表第i天持有股票的最大收益
// dp[i][1]代表第i天不持有股票的最大收益
int[][] dp = new int[2][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < len; i++){
dp[i % 2][0] = Math.max(dp[(i-1) % 2][0], -prices[i]);
dp[i % 2][1] = Math.max(dp[(i-1) % 2][1], prices[i] + dp[(i-1) % 2][0]);
}
return dp[(len-1) % 2][1];
}
}
122.買賣股票的最佳時機II
思路
dp數(shù)組的含義：
- dp[i][0] 表示第i天持有股票所得現(xiàn)金。
- dp[i][1] 表示第i天不持有股票所得最多現(xiàn)金
注意這里和121. 買賣股票的最佳時機 (opens new window)唯一不同的地方笔链，就是推導dp[i][0]的時候段只，第i天買入股票的情況。 - 本題鉴扫，因為一只股票可以買賣多次赞枕，所以當?shù)趇天買入股票的時候，所持有的現(xiàn)金可能有之前買賣過的利潤坪创。
那么第i天持有股票即dp[i][0]炕婶，如果是第i天買入股票，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 減去 今天的股票價格 即：dp[i - 1][1] - prices[i]莱预。
再來看看如果第i天不持有股票即dp[i][1]的情況柠掂， 依然可以由兩個狀態(tài)推出來- 第i-1天就不持有股票，那么就保持現(xiàn)狀依沮，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：dp[i - 1][1]
- 第i天賣出股票涯贞，所得現(xiàn)金就是按照今天股票價格賣出后所得現(xiàn)金即：prices[i] + dp[i - 1][0]
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int[2];
// 0代表持有，1代表賣出
dp[0] = -prices[0];
dp[1] = 0;
for(int i = 1; i <= prices.length; i++){
//第i天持有; 或前一天持有（前一天持有的話危喉，之前就是賣出的狀態(tài)宋渔，就要用dp[1]減去前一天的價格）
dp[0] = Math.max(dp[0], dp[1] - prices[i - 1]);
//第i天賣出；或前一天賣出(前一天賣出的話姥饰，先前就是持有的狀態(tài)傻谁，再加上前一天的收益)
dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);
}
return dp[1]; //二維數(shù)組應該返回length-1，但是這里改了for循環(huán)里 i <= prices.length
}
}
123.買賣股票的最佳時機III
這道題一下子就難度上來了列粪，關(guān)鍵在于至多買賣兩次审磁，這意味著可以買賣一次，可以買賣兩次岂座，也可以不買賣态蒂。
文章講解
思路
- 關(guān)鍵在于至多買賣兩次，這意味著可以買賣一次费什，可以買賣兩次钾恢，也可以不買賣。
-
確定dp數(shù)組以及下標的含義
一天一共就有五個狀態(tài)，- 沒有操作 （其實我們也可以不設(shè)置這個狀態(tài)）
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
dp[i][j]中 i表示第i天瘩蚪，j為 [0 - 4] 五個狀態(tài)泉懦，dp[i][j]表示第i天狀態(tài)j所剩最大現(xiàn)金。
需要注意：dp[i][1]疹瘦，表示的是第i天崩哩，買入股票的狀態(tài)，并不是說一定要第i天買入股票
確定遞推公式
-
達到dp[i][1]狀態(tài)言沐，有兩個具體操作：
- 操作一：第i天買入股票了邓嘹，那么
dp[i][1] = dp[i-1][0] - prices[i] - 操作二：第i天沒有操作，而是沿用前一天買入的狀態(tài)险胰，即：
dp[i][1] = dp[i - 1][1] - dp[i][1]一定是選最大的汹押，所以
dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
- 操作一：第i天買入股票了邓嘹，那么
-
同理dp[i][2]也有兩個操作：
- 操作一：第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])
- 操作一：第i天賣出股票了，那么
同理可推出剩下狀態(tài)部分：
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
dp數(shù)組如何初始化
第0天沒有操作，這個最容易想到榆综，就是0鸟悴，即：dp[0][0] = 0;
第0天做第一次買入的操作，dp[0][1] = -prices[0];
第0天做第一次賣出的操作奖年，這個初始值應該是多少呢？
此時還沒有買入沛贪，怎么就賣出呢陋守？ 其實大家可以理解當天買入，當天賣出利赋，所以dp[0][2] = 0;
第0天第二次買入操作水评，初始值應該是多少呢？應該不少同學疑惑媚送，第一次還沒買入呢中燥，怎么初始化第二次買入呢？
第二次買入依賴于第一次賣出的狀態(tài)塘偎，其實相當于第0天第一次買入了疗涉，第一次賣出了，然后再買入一次（第二次買入）吟秩，那么現(xiàn)在手頭上沒有現(xiàn)金咱扣，只要買入，現(xiàn)金就做相應的減少涵防。
所以第二次買入操作闹伪，初始化為：dp[0][3] = -prices[0];
同理第二次賣出初始化dp[0][4] = 0;確定遍歷順序
從遞歸公式其實已經(jīng)可以看出，一定是從前向后遍歷，因為dp[i]偏瓤，依靠dp[i - 1]的數(shù)值杀怠。-
舉例推導dp數(shù)組
以輸入[1,2,3,4,5]為例
image.png
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
/*
* 定義 5 種狀態(tài):
* 0: 沒有操作, 1: 第一次買入, 2: 第一次賣出, 3: 第二次買入, 4: 第二次賣出
*/
int[][] dp = new int[len][5];
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for(int i = 1; i < len; i++){
dp[i][1] = Math.max(dp[i - 1][1], 0 - prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[len - 1][4];
}
}
