给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000
二维数组-动态规划
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.empty()){
return 0;
}
int n = prices.size();
k = min(k , n/2);
vector<vector<int>> buy(n+1, vector<int>(k+1));
vector<vector<int>> sell(n+1, vector<int>(k+1));
buy[0][0] = -prices[0];
sell[0][0] = 0;
for(int i = 1; i <= k; k++){
buy[0][i] = sell[0][i] = INT_MIN / 2;
}
for(int i = 1; i < n; i++){
buy[i][0] = max(buy[i-1][0], sell[i-1][0] - prices[i]);
for(int j = 1; j <= k; j++){
buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i]);
sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i]);
}
}
return *max_element(sell[n-1].begin(), sell[n-1].end());
}
};
时间复杂度：O(nmin(n,k))，其中 n 是数组 prices 的大小
空间复杂度：O(nmin(n,k))
这道题我们使用两个二维向量来记录状态。
我们定义动态数组buy[i][j]，含义是在第i天的时候，持有股票（不一定是当天买）并储存最大利润，然后一共有完整的交易j次（完整的交易指的是经过买和卖）。
sell[i][j]的含义是在第i天的时候，没有持有股票并储存最大利润，然后一共有完整的交易j次。
那么buy的动态转换方程从何而来呢？我们如何能在第i天持有股票？我们可以选择今天不进行操作，保留前一天的持股情况max(buy[i-1][j], sell[i-1][j] - prices[i])，我们也可以选择今天买入股票，由于题目说必须在再次购买前出售掉之前的股票，就说明前一天是没有持有股票的，然后在减去今天买的股票价格prices[i]。
sell的动态转换方程，我们要如何在第i天没有持有股票？有两种情况，一种是今天不进行操作，那么说明昨天也是没有持有股票sell[i-1][j]。一种是今天卖掉股票，说明前一天持有股票，buy[i-1][j-1] + prices[i]，然后再加上今天的股价。要注意的是由于我们第i天进行了卖操作才完成了第j次完整操作，则前一天持股的时候，已经有了j-1次完整操作。
有几个细节要注意的是，我们是从第0天而不是第一天开始，然后我们第0天的时候，不可能有完整的操作（最多进行一次买操作），所以第0天 buy[0][i]都要设为不可能达到的最小值。
还有我们的完整操作次数k，最多不会超过prices容量的一半（因为一天最多进行买或者卖，一次完整操作最少需要两天）。
以及为何sell[i][0]不用计算，因为当sell发生的时候，不可能没有完整的交易。
优化：滚动数组
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.empty()) {
return 0;
}
int n = prices.size();
k = min(k, n / 2);
vector<int> buy(k + 1);
vector<int> sell(k + 1);
buy[0] = -prices[0];
sell[0] = 0;
for (int i = 1; i <= k; ++i) {
buy[i] = sell[i] = INT_MIN / 2;
}
for (int i = 1; i < n; ++i) {
buy[0] = max(buy[0], sell[0] - prices[i]);
for (int j = k; j >= 1; j--) {
buy[j] = max(buy[j], sell[j] - prices[i]);
sell[j] = max(sell[j], buy[j - 1] + prices[i]);
}
}
return *max_element(sell.begin(), sell.end());
}
};
空间复杂度优化为 O(min(n,k))。
由于buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i]);依赖于buy上一行第j个元素和sell的上一行第j个元素，所以可以优化为buy[j] = max(buy[j], sell[j] - prices[i]);。 sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i])依赖于上一行的sell的上一行第j个元素和buy的上一行的j-1个元素，所以我们可以通过倒序遍历，并优化代码为sell[j] = max(sell[j], buy[j - 1] + prices[i]); 。