本文主要是介绍day51 动态规划part12 ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费 ●总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一遍过
class Solution {
public:int maxProfit(vector<int>& prices) {int len=prices.size();vector<vector<int>> dp(len+1,vector<int>(3,0));dp[0][2]=0;dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<len;i++){dp[i][0]=max(dp[i-1][2]-prices[i],dp[i-1][0]);dp[i][1]=max(dp[i-1][0]+prices[i],dp[i-1][1]);dp[i][2]=max(dp[i-1][1],dp[i-1][2]);}return max(dp[len-1][2],dp[len-1][1]);}
};
也可以划成四个状态:
- 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有)
- 不持有股票状态,这里就有两种卖出股票状态
- 状态二:保持卖出股票的状态(两天前就卖出了股票,度过一天冷冻期。或者是前一天就是卖出股票状态,一直没操作)
- 状态三:今天卖出股票
- 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!
递推公式列表
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];
一遍过,只是多了手续费。
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int len=prices.size();vector<vector<int>> dp(len+1,vector<int>(2,0));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<len;i++){dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);}return dp[len-1][1];}
};
股票问题总结:
动态规划:121.买卖股票的最佳时机 (opens new window),股票只能买卖一次,问最大利润。
【贪心解法】
取最左最小值,取最右最大值,那么得到的差值就是最大利润
【动态规划】
- dp[i][0] 表示第i天持有股票所得现金。
- dp[i][1] 表示第i天不持有股票所得现金。
如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来
- 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
- 第i天买入股票,所得现金就是买入今天的股票后所得现金即:-prices[i] 所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
如果第i天不持有股票即dp[i][1], 也可以由两个状态推出来
- 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
- 第i天卖出股票,所得现金就是按照今天股票佳价格卖出后所得现金即:prices[i] + dp[i - 1][0] 所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
动态规划:122.买卖股票的最佳时机II (opens new window)可以多次买卖股票,问最大收益。
【贪心解法】
收集每天的正利润便可
class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;for (int i = 1; i < prices.size(); i++) {result += max(prices[i] - prices[i - 1], 0);}return result;}
};
【动态规划】
dp数组定义:
- dp[i][0] 表示第i天持有股票所得现金
- dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来
- 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
- 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]
注意这里和121. 买卖股票的最佳时机 (opens new window)唯一不同的地方,就是推导dp[i][0]的时候,第i天买入股票的情况。
在121. 买卖股票的最佳时机 (opens new window)中,因为股票全程只能买卖一次,所以如果买入股票,那么第i天持有股票即dp[i][0]一定就是 -prices[i]。
而本题,因为一只股票可以买卖多次,所以当第i天买入股票的时候,所持有的现金可能有之前买卖过的利润。
动态规划:123.买卖股票的最佳时机III (opens new window)最多买卖两次,问最大收益。
【动态规划】
一天一共就有五个状态,
- 没有操作
- 第一次买入
- 第一次卖出
- 第二次买入
- 第二次卖出
dp[i][j]中 i表示第i天,j为 [0 - 4] 五个状态,dp[i][j]表示第i天状态j所剩最大现金。
达到dp[i][1]状态,有两个具体操作:
- 操作一:第i天买入股票了,那么dp[i][1] = dp[i-1][0] - prices[i]
- 操作二:第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]也有两个操作:
- 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
动态规划:188.买卖股票的最佳时机IV (opens new window)最多买卖k笔交易,问最大收益。
使用二维数组 dp[i][j] :第i天的状态为j,所剩下的最大现金是dp[i][j]
j的状态表示为:
- 0 表示不操作
- 1 第一次买入
- 2 第一次卖出
- 3 第二次买入
- 4 第二次卖出
- .....
除了0以外,偶数就是卖出,奇数就是买入。
- 确定递推公式
达到dp[i][1]状态,有两个具体操作:
- 操作一:第i天买入股票了,那么dp[i][1] = dp[i - 1][0] - prices[i]
- 操作二:第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]也有两个操作:
- 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
动态规划:309.最佳买卖股票时机含冷冻期 (opens new window)可以多次买卖但每次卖出有冷冻期1天。
相对于动态规划:122.买卖股票的最佳时机II (opens new window),本题加上了一个冷冻期。
在动态规划:122.买卖股票的最佳时机II (opens new window)中有两个状态,持有股票后的最多现金,和不持有股票的最多现金。本题则可以花费为四个状态
dp[i][j]:第i天状态为j,所剩的最多现金为dp[i][j]。
具体可以区分出如下四个状态:
- 状态一:买入股票状态(今天买入股票,或者是之前就买入了股票然后没有操作)
- 卖出股票状态,这里就有两种卖出股票状态
- 状态二:两天前就卖出了股票,度过了冷冻期,一直没操作,今天保持卖出股票状态
- 状态三:今天卖出了股票
- 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!
达到买入股票状态(状态一)即:dp[i][0],有两个具体操作:
- 操作一:前一天就是持有股票状态(状态一),dp[i][0] = dp[i - 1][0]
- 操作二:今天买入了,有两种情况
- 前一天是冷冻期(状态四),dp[i - 1][3] - prices[i]
- 前一天是保持卖出股票状态(状态二),dp[i - 1][1] - prices[i]
所以操作二取最大值,即:max(dp[i - 1][3], dp[i - 1][1]) - prices[i]
那么dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
达到保持卖出股票状态(状态二)即:dp[i][1],有两个具体操作:
- 操作一:前一天就是状态二
- 操作二:前一天是冷冻期(状态四)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
达到今天就卖出股票状态(状态三),即:dp[i][2] ,只有一个操作:
- 操作一:昨天一定是买入股票状态(状态一),今天卖出
即:dp[i][2] = dp[i - 1][0] + prices[i];
达到冷冻期状态(状态四),即:dp[i][3],只有一个操作:
- 操作一:昨天卖出了股票(状态三)
p[i][3] = dp[i - 1][2];
动态规划:714.买卖股票的最佳时机含手续费 (opens new window)可以多次买卖,但每次有手续费。
相对于动态规划:122.买卖股票的最佳时机II (opens new window),本题只需要在计算卖出操作的时候减去手续费就可以了,代码几乎是一样的。
唯一差别在于递推公式部分,所以本篇也就不按照动规五部曲详细讲解了,主要讲解一下递推公式部分。
这里重申一下dp数组的含义:
dp[i][0] 表示第i天持有股票所省最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来
- 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
- 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]
所以:dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
在来看看如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来
- 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
- 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金,注意这里需要有手续费了即:dp[i - 1][0] + prices[i] - fee
所以:dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
本题和动态规划:122.买卖股票的最佳时机II (opens new window)的区别就是这里需要多一个减去手续费的操作。
总结:从买卖一次到买卖多次,从最多买卖两次到最多买卖k次,从冷冻期再到手续费。
这篇关于day51 动态规划part12 ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费 ●总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!