合肥做公司网站公司seowhy官网

题目来源：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

C++题解：动态规划

思路同力扣 123. 买卖股票的最佳时机 III-CSDN博客，只是把最高2次换成k次。如果思路不清晰，可以将k从0写到4等找找规律。

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();if(n <= 1) return 0;// dp[i][j], 当j为偶数表示第j/2+1次买入，奇数表示(j+1)/2次卖出vector< vector<int> > dp(n, vector<int>(2*k, 0));for(int j = 0; j < k; j++) {dp[0][j*2] = -prices[0]; //初始化}for(int i = 1; i < n; i++) {dp[i][0] = max(dp[i-1][0], -prices[i]);for(int j = 1; j < k; j++){dp[i][2*j] = max(dp[i-1][2*j], dp[i-1][2*j-1] - prices[i]);}for(int m = 0; m < k; m++) {dp[i][2*m+1] = max(dp[i-1][2*m+1], dp[i-1][2*m] + prices[i]);}}return dp[n-1][2*k-1];}
};