提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
一、123买卖股票的最佳时机III
超时了。。。
class Solution {
public:
int helper(vector<int>& prices, int start, int end) {
int profit = 0;
int buyPrice = prices[start];
for (int i = start + 1; i < end; i ++) {
profit = max(profit, prices[i] - buyPrice);
buyPrice = min(buyPrice, prices[i]);
}
return profit;
}
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i ++) {
if (prices[i] <= prices[i-1]) {
continue;
}
result = max(result, helper(prices, 0, i) + helper(prices, i - 1, prices.size()));
}
return result;
}
};
二维dp:
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < prices.size(); i ++) {
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]);
}
// for (auto vec: dp) {
// for (int num: vec) cout << num << " ";
// cout << endl;
// }
return dp[prices.size()-1][4];
}
};
二、188买卖股票的最佳时机IV
上一道题举一反三即可,但上一道题的二维dp真滴想不到呀。。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(1 + 2 * k, 0));
for (int i = 1; i < dp[0].size(); i += 2) {
dp[0][i] = -prices[0];
}
for (int i = 1; i < prices.size(); i ++) {
for (int j = 1; j < dp[0].size(); j ++) {
if (j % 2 == 1) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
}
else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i]);
}
}
}
// for (auto vec: dp) {
// for (int num: vec) cout << num << " ";
// cout << endl;
// }
return dp[prices.size() - 1][2 * k];
}
};