LeetCode 188 Best Time to Buy and Sell Stock IV
题目分析
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
分析可知，我们应仅当在谷底处买入，谷峰处卖出股票，期间可以有波动，但是不能低于起始处。
我们首先找出所有满足上述条件的最优买入卖出段，之后排序求出最大的 k 个的和即可。
以上分析有一处错误，期间可以有波动，实际上波动前后分两次买卖可以比一次买卖赚更多。
补救方法是，将波动视为一次买入卖出段，也参与排序。
但是这样搞之后，算法变得复杂，我们需要在 one pass 中记录这种波动的幅度。
不想再继续搞的有问题解法
三连 WA，有毒吧，不玩了，睡觉了。
https://leetcode.com/submissions/detail/633771632/
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<int> profits;
int buy = prices[0];
int sell = buy;
bool downing = false;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] < buy) {
downing = false;
if (sell - buy > 0) {
profits.push_back(sell - buy);
}
buy = prices[i];
sell = buy;
} else if (prices[i] > sell) {
if (downing) {
downing = false;
profits.push_back(sell - prices[i - 1]);
}
sell = prices[i];
} else if (prices[i] < sell) {
downing = true;
}
}
if (sell - buy > 0) {
profits.push_back(sell - buy);
}
sort(profits.rbegin(), profits.rend());
int ans = 0;
for (int i = 0; i < profits.size() && i < k; i++) {
ans += profits[i];
}
return ans;
}
};
动态规划法
参考 https://labuladong.gitee.io/algo/1/12/ ，
- 状态：第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态
- 选择：买入、卖出、无操作
- base case：实际上只需要处理第 0 天时已经持有股票的情况。
实现中，我为了清晰期间 dp 数组的索引直接与对应的意义对应，不需要再减一，但是我忘了 prices 可不是这样搞的，看了好久才发现这个 bug。
下面的一个优化是 k 实际上可以缩小成 d / 2，因为就算没有人为限制交易次数，天数依然会对其进行限制。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
// state: day d, used times t, 1 / 0 have stock or not
vector<vector<vector<int>>> dp(prices.size() + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));
for (int t = 0; t <= k; t++) {
dp[0][t][1] = INT_MIN;
}
for (int d = 1; d <= prices.size(); d++) {
for (int t = 1; t <= k; t++) {
dp[d][t][0] = max(dp[d-1][t][0], dp[d-1][t][1] + prices[d - 1]);
dp[d][t][1] = max(dp[d-1][t][1], dp[d-1][t-1][0] - prices[d - 1]);
}
}
int ans = 0;
for (int i = 0; i <= k; i++) {
ans = max(ans, dp[prices.size()][i][0]);
}
return ans;
}
};