188. 買賣股票的最佳時機 IV

給你一個整數數組?prices?和一個整數?k?，其中?prices[i]?是某支給定的股票在第?i?天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成?k?筆交易。也就是說，你最多可以買?k?次，賣?k?次。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1：

輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。

示例 2：

輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。隨后，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。

提示：

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

思路:

1.確定dp數組以及下標的含義

使用二維數組 dp[i][j] ：第i天的狀態為j，所剩下的最大現金是dp[i][j]

j的狀態表示為：

0 表示不操作
1 第一次持有
2 第一次賣出
3 第二次持有入
4 第二次賣出
.....
題目要求是至多有K筆交易，那么j的范圍就定義為 2 * k + 1 就可以了

2.確定遞推公式

達到dp[i][1]狀態，有兩個具體操作：

1)操作一：第i天買入第一支股票了，那么dp[i][1] = dp[i-1][0] - prices[i]

2)操作二：第i天沒有操作，而是沿用前一天買入第一支股票的狀態，即：dp[i][1] = dp[i - 1][1]

達到dp[i][2]狀態，有兩個具體操作：

1)操作一：第i天賣出第一支股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]

2)操作二：第i天沒有操作，沿用前一天賣出第一支股票的狀態，即：dp[i][2] = dp[i - 1][2]

達到dp[i][3]狀態，有兩個具體操作：

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

達到dp[i][4]狀態，有兩個具體操作：

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

........同理可以類比剩下的狀態

if(i%2==1)

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);//買入

if(i%2==0)

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);//賣出

3.dp數組如何初始化

可以推出dp[0][j]當j為奇數的時候都初始化為 -prices[0]

4.確定遍歷順序

從遞歸公式其實已經可以看出，一定是從前向后遍歷，因為dp[i]，依靠dp[i - 1]的數值。

5.舉例

k=2,prices=[1,2,3,4]

代碼參考:

class Solution {public int maxProfit(int k, int[] prices) {int[][] dp=new int[prices.length][2*k+1];//初始化for(int i=1;i<2*k+1;i=i+2){dp[0][i]=-prices[0];}for(int i=1;i<prices.length;i++){
for(int j=1;j<2*k+1;j++){//奇數買入
if( j%2==1){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
}//偶數賣出if(j%2==0){dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]+prices[i]);}
}}return dp[prices.length-1][2*k];}
}

---

309. 買賣股票的最佳時機含冷凍期

給定一個整數數組prices，其中第??prices[i]?表示第?i?天的股票價格 。?

設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

• 賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: prices = [1,2,3,0,2]
輸出: 3 
解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出]

示例 2:

輸入: prices = [1]
輸出: 0

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

思路:

將交易狀態化為四種

動態規劃五部曲:

1.確定dp數組以及下標的含義

dp[i][j]，第i天狀態為j，所剩的最多現金為dp[i][j]。

j=0:今天購入了股票/以前購買了股票還沒賣出

j=1:今天賣出股票

j=2:冷凍期

j=3:今天沒有股票在手,且不是今天賣出的股票

2.確定遞推公式

dp[i][0]=max(dp[i-1][0],dp[i-1][3]-prices[i],dp[i-1][2]-prices[i])

dp[i][1]=dp[i-1][0]

dp[i][2]=dp[i-1][1]

dp[i-1][3]=max(dp[i-1][3],dp[i-1][2])

3.初始化

dp[0][0]=-prices[0]

dp[0][1]=0

dp[0][2]=0

dp[0][3]=0

4.遍歷順序

從遞歸公式上可以看出，dp[i] 依賴于 dp[i-1]，所以是從前向后遍歷。

5.舉例

代碼參考:

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][4];//初始化dp[0][0]=0-prices[0];dp[0][1]=0;dp[0][2]=0;dp[0][3]=0;for(int i=1;i<prices.length;i++){dp[i][0]=Math.max(Math.max(dp[i-1][0],dp[i-1][2]-prices[i]),dp[i-1][3]-prices[i]);dp[i][1]=dp[i-1][0]+prices[i];dp[i][2]=dp[i-1][1];dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]);} int n=prices.length;int result=Math.max(Math.max(dp[n-1][3],dp[n-1][2]),dp[n-1][1]);return result;    }
}

---

714. 買賣股票的最佳時機含手續費

給定一個整數數組?prices，其中?prices[i]表示第?i?天的股票價格 ；整數?fee?代表了交易股票的手續費用。

你可以無限次地完成交易，但是你每筆交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。

返回獲得利潤的最大值。

注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續費。

示例 1：

輸入：prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出：8
解釋：能夠達到的最大利潤:  
在此處買入?prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤:?((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

輸入：prices = [1,3,7,5,10,3], fee = 3
輸出：6

提示：

• 1 <= prices.length <= 5 * 104
• 1 <= prices[i] < 5 * 104
• 0 <= fee < 5 * 104

思路:

手續費相當于也是買股票的成本的一部分

動態規劃五部曲:

1.確定dp數組以及下標的含義

dp[i][0]，第i天狀態為持有/購買股票,能夠達到的最大利潤

dp[i][1]，第i天狀態為不持有/賣出股票,能夠達到的最大利潤

2.確定遞推公式

dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]-fee)

dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i])

3.初始化

dp[0][0]=-prices[0]-fee

dp[0][1]=0

4.遍歷順序

從遞歸公式上可以看出，dp[i] 依賴于 dp[i-1]，所以是從前向后遍歷。

5.舉例

代碼參考:

class Solution {public int maxProfit(int[] prices, int fee) {int[][] dp= new int[prices.length][2];//初始化dp[0][0]=0-prices[0];dp[0][1]=0;//for(int i=1;i<prices.length;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);}return dp[prices.length-1][1];}
}