代码随想录算法训练营第四十二天-动态规划-股票-188.买卖股票的最佳时机IV

• 题目要求进行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];}
};

• 汇总