- 题目要求进行k次买卖
- 其实就是上一题的扩展，把2次扩展为k次
- 定义动规数组依然是二维，第一个维度表示第几天，第二个维度表示第几次买入和卖出
- 所以第二个维度的长度应该是
2k+1 - 在for循环内，要使用一个内循环来表示第几次买入或卖出，根据上一题的过程，可以发现其中的规律
class Solution {
public:
int maxProfit(int k, std::vector<int>& prices) {
int len = prices.size();
if (len == 0) {
return 0;
}
std::vector<std::vector<int>> dp(len, std::vector<int>(2 * k + 2, 0));
for (int i = 0; i < 2 * k; i += 2) {
dp[0][i + 1] = -prices[0];
}
for (int i = 1; i < len; ++i) {
for (int j = 0; j < 2 * k; j += 2) {
dp[i][j + 1] = std::max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = std::max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[len - 1][2 * k];
}
};
