给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
时间: 2024-05-24 13:10:31 浏览: 128
动态规划算法:
定义状态:dp[i][j][0/1] 表示前i天交易了j次时,是否持有股票的最大利润。
状态转移方程:
- dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
- dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
初始状态:
- dp[0][j][0] = 0
- dp[0][j][1] = INT_MIN
- dp[i][0][0] = 0
- dp[i][0][1] = INT_MIN
最终结果为:dp[n][k][0]
时间复杂度为 O(n*k),空间复杂度为 O(n*k)。
C++ 代码如下:
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (k >= n / 2) { // 如果 k 大于等于 n/2,相当于可以进行任意多次交易,问题转化为无限次交易问题
int res = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i-1])
res += prices[i] - prices[i-1];
}
return res;
}
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(2)));
for (int i = 0; i <= k; i++) {
dp[0][i][0] = 0;
dp[0][i][1] = INT_MIN;
}
for (int i = 1; i <= n; i++) {
dp[i][0][0] = 0;
dp[i][0][1] = INT_MIN;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1]);
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1]);
}
}
return dp[n][k][0];
}
};