面试经典150题 P188 买卖股票的最佳时机 IV

---

时间轴

时间轴

2025-12-17

init

动态规划

---

题目：

P188 买卖股票的最佳时机 IV

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/?envType=study-plan-v2&envId=top-interview-150

和下面这题类似：

P123 买卖股票的最佳时机 III

https://even629.com/posts/123/

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        int maxProfit(int k, vector<int> &prices)
        {
                int i, j, n = prices.size();
                int nr_state = 2 * k + 1;
                if (n == 1) {
                        return 0;
                }
                // dp[i][j]表示第i天的第j个状态的最大利润
                vector<vector<int> > dp(n, vector<int>(nr_state, 0));
                dp[0][0] = 0;
                dp[0][1] = -prices[0];
                for (j = 2; j < nr_state; j++) {
                        dp[i][j] = -1e9;
                }

                for (i = 1; i < n; i++) {
                        dp[i][0] = dp[i - 1][0];
                        for (j = 1; j < nr_state; j += 2) {
                                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                        }
                        for (j = 2; j < nr_state; j += 2) {
                                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                        }
                }
                return *std::max_element(dp[n - 1].begin(), dp[n - 1].end());
        }
};