目錄
- 121. 買賣股票的最佳時機
- 貪心
- dp思路
- 滾動數組優化
- 122. 買賣股票的最佳時機 II
- 123. 買賣股票的最佳時機 III
- 188. 買賣股票的最佳時機 IV
- 309. 最佳買賣股票時機含冷凍期
- 714. 買賣股票的最佳時機含手續費
121. 買賣股票的最佳時機
貪心
取最左最小值,取最右最大值,差值為最大利潤
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int minprice = prices[0];int maxpro = 0;for(int i = 1; i < n; i++){minprice = min(prices[i],minprice);maxpro = max(prices[i]-minprice,maxpro);}return maxpro;}
};
dp思路
step1:dp[i][0]
表示第i天持有股票最大所得現金。本題中只能買賣一次,所以買入后金額為-price[i]
。
dp[i][1]
表示第i天不持有股票最大所得現金。持有不等同于買入。
step2:
如果第i天持有股票dp[i][0]
可以由兩個狀態得到。
case1:第i-1持有股票,保持現狀,dp[i][0] = dp[i-1][0]
case2:第i天買入股票,所得現金就是買入今天的股票后所得現金。即dp[i][0] = -price[i]
dp[i][0] = max(dp[i-1][0],-price[i])
;
如果第i天不持有股票dp[i][1]
可以由兩個狀態得到。
case1: 第i-1不持有股票,保持現狀,dp[i][1] = dp[i-1][1]
case2: 第i-1持有股票,第i天賣出,dp[i][1] = dp[i-1][0] + price[i]
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+price[i])
step3:
初始狀態為dp[0][0]
:第0天持有股票的金額 = -prices[0]
dp[0][1]
第0天不持有股票的金額 = 0;
最終結果dp[n][1]
而不是dp[n][0]
,是因為最終必須要把股票賣出才能有收益。不賣出一定更虧。
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < n; i++){//持有dp[i][0] = max(dp[i-1][0],-prices[i]);//不持有dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[n-1][1];}
};
滾動數組優化
由于只用到了dp[i] 與dp[i-1]兩個狀態,所以只需一個2 * 2的數組即可。
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(2,vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < n; i++){//持有dp[i % 2][0] = max(dp[(i-1)%2][0],-prices[i]);//不持有dp[i % 2][1] = max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i]);}return dp[(n-1)%2][1];}
};
122. 買賣股票的最佳時機 II
dp[i][0]
:第i天持有股票獲取的最大現金
dp[i][1]
:第i天不持有股票所得的最多現金
如果第i天持有股票,則dp[i][0]
可以由兩個狀態推導;
case1:第i-1天就持有股票,保持現狀,則dp[i][0] = dp[i-1][0]
case2:第i天買入股票,現金則為昨天不持有股票所得現金減去今天股票價格dp[i][0] = dp[i-1][1] - prices[i]
如果第i天不持有股票,則dp[i][1]
可以由兩個狀態推導;
case1:第i-1天不持有股票,保持現狀,dp[i][1] = dp[i-1][1]
case2:第i-1天持有股票,第i天賣出,dp[i][1] = dp[i-1][0] + prices[i]
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(2,vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < n; i++){dp[i%2][0] = max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i]);dp[i%2][1] = max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i]);}return dp[(n-1)%2][1];}
};
123. 買賣股票的最佳時機 III
至多買賣兩次,即可以買賣一次,也可以買賣兩次,也可以不買賣。
每一天由五個狀態:
0、沒有操作
1、第一次買入
2、第一次賣出
3、第二次買入
4、第二次賣出
dp[i][j]
:i表示第i天,j為[0-4]五個狀態,dp[i][j]
表示第i天狀態j所剩最大現金。
2、確定遞推公式
舉例dp[i][1]
:表示第i天,買入股票的狀態,并不是說一定要第i天買入股票。
達到dp[i][1]
狀態,有兩個具體操作:
case1:第i天買入股票,那么dp[i][1] = dp[i-1][0] - prices[i]
case2:第i天沒有操作,那么dp[i][1] = dp[i-1][1]
dp[i-1][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])
;
同理dp[i][2]
也有兩個操作:
case1:第i天賣出股票了,那么dp[i][2] = dp[i-1][1] + prices[i]
case2:第i天沒有操作,沿用前一天賣出股票的狀態,即:dp[i][2] = dp[i-1][2]
所以dp[i][2] = max(dp[i-1][1] + prices[i],dp[i-1][2])
同理dp[i][3]
也有兩個操作:
case1:第i天買入股票,dp[i][3] = dp[i-1][2] - prices[i]
case2:第i天沒有操作,沿用前一天買入股票的狀態,即:dp[i][3] = dp[i-1][3]
同理dp[i][4]
也有兩個操作:
case1:第i天賣出股票,dp[i][4] = dp[i-1][3] + prices[i]
case2:第i天沒有操作,沿用前一天賣出股票的狀態,即:dp[i][4] = dp[i-1][4]
那么如何初始化呢?
第0天沒有操作的話,dp[0][0] = 0
第0天做第一次買入操作的話,dp[0][1] = -prices[0]
第0天做第一次賣出的操作,這個初始值為0。
第0天第二次買入,不管幾次,手頭上沒有錢,只能減少dp[0][3] = -prices[0]
第0天第二次賣出,dp[0][4] = 0
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(5,0));//dp[0][0] = 0;dp[0][1] = -prices[0];//dp[0][2] = 0;dp[0][3] = -prices[0];//dp[0][4] = 0;for(int i = 1; i < n; i++){dp[i][0] = dp[i-1][0];dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[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]);}return dp[n-1][4];}
};
188. 買賣股票的最佳時機 IV
step1:
這一題為上一題的進階版本,定義二維dp數組。
使用二維數組dp[i][j]
:第i天的狀態為j,所剩下的最大現金是dp[i][j]
j的狀態表示為:
0不操作、1第一次買入、2第一次賣出、…
除了0以外,偶數就是賣出,奇數就是買入。因為是最多有k筆交易,所以j的范圍就定義為2*k+1.
vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));
step2:
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]);
}
step3:
初始化,只要是買入操作,現金就會相應減少,賣出操作初值均為0
for(int j = 1; j < 2*k; j += 2)
{dp[0][j] = -prices[0];
}
AC代碼:
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();if(n == 0 || k == 0) return 0; vector<vector<int>> dp(n,vector<int>(k*2+1,0));for(int i = 1; i <= 2*k; i += 2)dp[0][i] = -prices[0];for(int i = 1; i < n; i++){for(int j = 0; j <= 2 * k - 2; 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]);}}return dp[n-1][2*k];}
};
309. 最佳買賣股票時機含冷凍期
狀態一:買入股票狀態(可能是今天買入的,也有可能是之前就買入了然后沒有操作)
對于賣出股票狀態,有兩種:
狀態二:兩天前就賣出了股票,度過了冷凍期,然后一直沒有操作,今天仍然保持賣出股票狀態
狀態三:今天賣出了股票
狀態四:今天為冷凍期狀態,但冷凍期狀態不可持續,只有一天
遞推公式如下:
到達買入股票狀態(狀態一)即dp[i][0]
,有兩個具體操作:
case1:前一天就是這個狀態,今天沿用該狀態dp[i][0] = dp[i-1][0]
case2:今天買入,有兩種情況(狀態四)
前一天是冷凍期,前一天是保持賣出股票的狀態(狀態二),這兩個情況今天都有可能買入
即:dp[i][0] = max(dp[i-1][0],max(dp[i-1][3],dp[i-1][1])-prices[i])
到達保持賣出狀態(狀態二)即:dp[i][1]
,有兩個具體操作:
case1:前一天就是狀態二,沿用該狀態
case2:前一天是冷凍期(狀態四)
dp[i][1] = 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]
綜上的遞推代碼為:
dp[i][0] = max(dp[i-1][0],max(dp[i-1][3],dp[i-1][1])-prices[i]);
dp[i][1] = 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];
關于dp數組的初始化:
狀態一,持有股票,那么dp[0][0] = -prices[0]
狀態二,保持賣出狀態,dp[0][1] = 0
狀態三,剛賣出股票,同樣不會有收入dp[0][2] = 0
狀態四,冷凍期,dp[0][3] = 0
最后的結果是從狀態二到狀態四中選取最大值。
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(4,0));dp[0][0] = -prices[0];for(int i = 1; i < n; i++){dp[i][0] = max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i]);dp[i][1] = 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 max(dp[n-1][1],max(dp[n-1][2],dp[n-1][3]));}
};
714. 買賣股票的最佳時機含手續費
與122. 買賣股票的最佳時機 II相比,多減去操作費用。
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<vector<int>> dp(2,vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < n; i++){//當天持有dp[i%2][0] = max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i]);//當天不持有dp[i%2][1] = max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i]-fee);}return dp[(n-1)%2][1];}
};