题目描述
假设你有一个数组,其中第 i 个元素表示第 i 天某个股票的价格。
设计一种算法以找到最大利润,可以完成最多 k 次交易,但必须先购买股票再出售股票,不能同时多次交易。
样例
Example 1:
Input: [2,4,1], k = 2
Output: 2
解释: 第一天买入(price = 2),第二天售出 (price = 4), 利润 = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
Output: 7
解释: 第二天买入(price = 2),第三天卖出 (price = 6), 利润 = 6-2 = 4.
接着第五天买入(price = 0),第六天卖出(price = 3), 利润 = 3-0 = 3.
算法
(动归) 从$O(kn^2)$优化到$O(kn)$
首先,假如一共有n天,那么最多买卖n/2次(因为买卖不能在同一天),因此如果k>n/2的话,可以直接k=n/2。
这个问题问的是不超过k次交易获得的最大利润,考虑动归,动归数组dp[k][i]表示考虑前i天,最多买卖k次能获得的最大收益。
于是动归转移方程为
dp[k][i] = max(dp[k][i-1], dp[k-1][j] + prices[i] - prices[j]) (枚举j,0<=j<i)
(因为假如最后一次交易不在第i天卖出,那么相当于没有考虑第i天,就是dp[k][i-1]的结果;假如在第i天卖出,那么就是枚举最后一次买卖时买入股票的日期j,然后在第i天卖出,再加上前j天买卖k-1次的情况。)
class Solution {
public:
int maxProfit(int K, vector<int>& prices) {
if (!prices.size())
return 0;
K = min(K, int(prices.size()) / 2);
vector<vector<int>> dp(K + 1, vector<int>(prices.size(), 0));
for (int k = 1; k <= K; k ++) {
for (int i = 1; i < prices.size(); i ++) {
dp[k][i] = dp[k][i-1];
for (int j = 0; j < i; j ++) { // 枚举第k次买卖时在哪天买入股票
dp[k][i] = max(dp[k][i], dp[k-1][j] + prices[i] - prices[j]);
}
}
}
return dp[K][prices.size()-1];
}
};
但是上面的做法的时间复杂度是$O(kn^2)$,会超时。
我们可以进一步优化,我们仔细观察会发现在求dp[k][i]
时,
dp[k][i] = max(dp[k][i-1], dp[k-1][j] + prices[i] - prices[j]) (枚举j, 0<=j<i)
其中max(dp[k-1][j] + prices[i] - prices[j]) 等价于 max(dp[k-1][j] - prices[j]) + prices[i]
最原始的方法中,我们是要遍历0到i,找到最大的dp[k-1][j] - prices[j],那么实际上只有最大的max_val = dp[k-1][j] - prices[j]有用,因此记录下最大的max_val即可,不需要每次都遍历0-i找最大。
这样省掉了一次枚举,时间复杂度变为$O(kn)$,空间复杂度仍为$O(kn)$。
class Solution {
public:
int maxProfit(int K, vector<int>& prices) {
if (!prices.size())
return 0;
K = min(K, int(prices.size()) / 2);
vector<vector<int>> dp(K+1, vector<int>(prices.size(), 0));
for (int k = 1; k <= K; k ++) {
int max_val = dp[k-1][0] - prices[0]; // 直接用max_val记录最大的dp[k-1][j] - prices[j]
for (int i = 1; i < prices.size(); i ++) { // 省掉了一次枚举
dp[k][i] = max(dp[k][i-1], max_val + prices[i]);
max_val = max(max_val, dp[k-1][i] - prices[i]); // 更新max_val
}
}
return dp[K][prices.size()-1];
}
};
进一步的,我们可以发现在求dp[k][i]
时,只用到dp[k-1][i]
,因此可以用滚动数组从空间上优化。空间优化为$O(n)$。
class Solution {
public:
int maxProfit(int K, vector<int>& prices) {
if (!prices.size())
return 0;
K = min(K, int(prices.size()) / 2);
vector<vector<int>> dp(2, vector<int>(prices.size(), 0)); // 滚动数组优化
for (int k = 1; k <= K; k ++) {
int max_delta = dp[0][0] - prices[0];
for (int i = 1; i < prices.size(); i ++) {
dp[1][i] = max(dp[1][i-1], max_delta + prices[i]);
max_delta = max(max_delta, dp[0][i] - prices[i]);
}
dp[0] = dp[1];
}
return dp[0][prices.size()-1];
}
};
太优美了这个优化!!
妙啊
有个疑问,一直想不明白,感觉像是状态方程定义的问题,如下:
dp[k][i] 表示前i天,最多买卖k次获得的最大收益。
我的疑问是在在第 i 天卖出情况的讨论
1. dp[k-1][j] + prices[i] - prices[j] 表示在第j天买入,然后加上前j天买卖k-1次的情况
这里dp[k-1][j] 表示的状态是 在j天有可能不交易,也有可能卖出。
那么如果在第j天买入,应该卖出的交易是在 j-1 天吧
所以我改了一下状态转移 dp[k-1][j-1] + prices[i] - prices[j] 这样需要申请 prices.size() + 1 个大小
我用我理解的改了一下代码,结果也是对的。
所以最后,就是想知道Corner同学定义的状态转移改怎样理解?
哈哈哈~ 本人比较笨,能帮忙解答一下不。
噢噢,我这里就是认为可以在同一天买入和卖出,比如在第a天买入,在第b天卖出,再在第b天买入,在第c天卖出,其实等价于在第a天买入然后第c天卖出。因为dp[k][i]的定义是前i天,最多买卖k次,假设dp[k-1][j]在第j天正好卖出了的话,相当于抵消掉了一次交易,也不违背最多买卖k次的要求,所以也是可以的。
你好,题解讲得很清楚~感谢~ 但是我还是这个问题,在第j天又卖出又买入的话,这样不就少了一次交易了吗?就不是k次了呀,不知道要怎么理解。
题目要求的是最多买卖k次获得的最大收益,包括dp[k][i]也是最多买卖k次,所以只要不大于k次就行了,不一定非要是k次
感觉写的特别清楚~
一步步将解法优化写的很清晰,可以套用的万能模板
哇谢谢呀~