【LeetCode】动态规划—188. 买卖股票的最佳时机 IV（附完整Python/C++代码）

if k >= len(prices) // 2:
    return solve_unlimited_transactions()

initialize dp array with dimensions (n, k+1, 2)
for each day i from 1 to n-1:
    for each transaction j from 1 to k:
        update dp[i][j][0] and dp[i][j][1] using state transition formulas
return dp[n-1][k][0]

class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        if not prices:
            return 0
        
        n = len(prices)

        # 当 k 大于等于 n/2 时，相当于可以进行无限次交易
        if k >= n // 2:
            max_profit = 0
            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    max_profit += prices[i] - prices[i - 1]
            return max_profit

        # 初始化 dp 数组
        dp = [[[0, 0] for _ in range(k + 1)] for _ in range(n)]
        
        # 初始化第一天的状态
        for j in range(1, k + 1):
            dp[0][j][1] = -prices[0]

        # 动态规划状态转移
        for i in range(1, n):
            for j in range(1, k + 1):
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])

        # 返回结果
        return dp[n - 1][k][0]

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // 当 k 大于等于 n/2 时，相当于可以进行无限次交易
        if (k >= n / 2) {
            int max_profit = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i - 1]) {
                    max_profit += prices[i] - prices[i - 1];
                }
            }
            return max_profit;
        }

        // 初始化 dp 数组
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2, 0)));

        // 初始化第一天的状态
        for (int j = 1; j <= k; ++j) {
            dp[0][j][1] = -prices[0];
        }

        // 动态规划状态转移
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }

        // 返回结果
        return dp[n - 1][k][0];
    }
};