🌗 188. 买卖股票的最佳时机 IV

难度: 🌗

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public int maxProfit(int k, int[] prices) {
        // 思路：
        // dp
        // 初始状态 - 始终未持有
        // 后续每笔交易均对应 2 种状态 -- 第 i 次持有 & 第 i 次卖出
        // 共 (2k + 1) 种状态
        int len = prices.length;
        // 特殊情况特判
        if(len == 0) {
            return 0;
        }
        k = Math.min(k, len);
        int[][] dp = new int[len][2 * k + 1];
        // 初始化 dp[0][j]
        for(int j = 0; j < 2 * k + 1; j ++) {
            if((j & 1) == 1) {
                dp[0][j] = - prices[0];
            }
        }
        // dp
        for(int i = 1; i < len; i ++) {
            dp[i][0] = 0;
            for(int j = 1; j < 2 * k + 1; j ++) {
                if((j & 1) == 1) {
                    // 持有状态
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                } else {
                    // 卖出状态
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                } 
            }
        }
        // 求 dp[len - 1][j] max
        int res = 0;
        for(int j = 0; j < 2 * k + 1; j ++) {
            res = Math.max(res, dp[len - 1][j]);
        }
        return res;
    }
}

---

输出