这一期是和上一期是连着的,包含的题目如下:
这三个题目所需要的思路是很相近的,先给出第一个的题目。
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
-
示例 1:
-
输入:prices = [3,3,5,0,0,3,1,4]
-
输出:6 解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3。
-
示例 2:
-
输入:prices = [1,2,3,4,5]
-
输出:4 解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
-
示例 3:
-
输入:prices = [7,6,4,3,1]
-
输出:0 解释:在这个情况下, 没有交易完成, 所以最大利润为0。
-
示例 4:
-
输入:prices = [1] 输出:0
提示:
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5
第一步——理解题意
就是给你一个数组,交易最多两次,获得最大金额。
第二步——思考递归状态
先看一下示例一:
示例 1:
输入:prices = [3,3,5,0,0,3,1,4]
输出:6 解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3。
我们可以把这个分为五部分——|3,3,5|0,0|3|1|4|
- 没有操作 (其实我们也可以不设置这个状态)——3,3,5
- 第一次持有股票——0,0
- 第一次不持有股票——3(此时正好卖出)
- 第二次持有股票——1
- 第二次不持有股票——4(此时正好卖出)
它们对应的递归公式是这样的:
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]);
第三步——进行初始化
dp[0][0]=0;(因为这个时候还什么都没干)
dp[0][1]=-prices[0];(因为这个时候买入第一次)
dp[0][2]=0;(先初始化为0,避免影响后面的赚的金额)
dp[0][3]=-prices[0];(也把它初始化为prices[0],是因为有可能整个数组只需要一次交易,不需要第二次交易)
dp[0][4]=0;(同理,先初始化为0,避免影响后面的赚的金额)
给出代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>>dp(len,vector<int>(5,0));
dp[0][1]=-prices[0];
dp[0][3]=-prices[0];
for(int i=1;i<len;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[len-1][4];
}
};
这个题目就到此结束了,但接下来还有两个跟他很相似的题目:
买卖股票的最佳时机IV
它和题1的不同就是把这个次数给抽象化了——你最多可以完成 k 笔交易
状态表示为:文章来源:https://www.toymoban.com/news/detail-803718.html
- 0 表示不操作
- 1 第一次买入
- 2 第一次卖出
- 3 第二次买入
- 4 第二次卖出
- .....
除了0以外,偶数就是卖出,奇数就是买入。
题目要求是至多有K笔交易,那么j的范围就定义为 2 * k + 1 就可以了。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
for (int i = 1;i < prices.size(); 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]);
}
}
return dp[prices.size() - 1][2 * k];
}
};
最佳买卖股票时机含冷冻期
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意这里是可以尽可能完成更多的交易,所以它这里是和买卖股票的最佳时机II相似,就是多了一个状态,有一天冷冻期。
状态表示为:
- 0 表示不操作
- 1 第一次买入
- 2 第一次卖出
- 3 第一次冷冻期
- 4 第二次买入
- .....
这里是没有次数的限制的文章来源地址https://www.toymoban.com/news/detail-803718.html
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
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][3] - prices[i], 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];
}
return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
}
};
到了这里,关于动态规划——买卖股票的最佳时机系列题Ⅱ的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!