LeetCode 每日一题笔记

0. 前言

• 日期：2025.12.17
• 题目：3573.买卖股票的最佳时机Ⅴ
• 难度：中等
• 标签：动态规划

1. 题目理解

问题描述：

示例：

2. 解题思路

核心观察

算法步骤

3. 代码实现

   public static long maximumProfit(int[] prices, int k) {
        int n = prices.length;

        // 定义三维DP数组：dp[i][j][s]
        // i：第i天（0~n-1）
        // j：已完成j笔交易（0~k）
        // s：持仓状态（0=无持仓，1=有持仓（做多），2=做空仓（做空））
        // 初始值设为极小值（表示不可达状态），用Long.MIN_VALUE/2避免溢出
        long[][][] dp = new long[n][k + 1][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][0] = Long.MIN_VALUE / 2;
                dp[i][j][1] = Long.MIN_VALUE / 2;
                dp[i][j][2] = Long.MIN_VALUE / 2;
            }
        }

        // 初始化第0天状态
        dp[0][0][0] = 0;               // 第0天，0笔交易，无持仓 → 利润0
        dp[0][0][1] = -prices[0]; // 第0天，0笔交易，买入持仓（做多）→ 利润=-股价
        dp[0][0][2] = prices[0];  // 第0天，0笔交易，卖空仓（做空）→ 利润=+股价

        // 核心：遍历每一天，处理状态转移
        for (int i = 1; i < n; i++) {
            // 遍历已完成的交易次数（0~k）
            for (int j = 0; j <= k; j++) {
                // ========== 状态0：第i天无持仓 ==========
                // 来源1：前一天也无持仓，不操作
                dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][j][0]);
                // 来源2：前一天有持仓（做多），今天卖出 → 完成1笔交易（j≥1）
                if (j >= 1) {
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][j-1][1] + prices[i]);
                }
                // 来源3：前一天做空仓，今天买回平仓 → 完成1笔交易（j≥1）
                if (j >= 1) {
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i-1][j-1][2] - prices[i]);
                }

                // ========== 状态1：第i天有持仓（做多） ==========
                // 来源1：前一天已有持仓，不操作
                dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j][1]);
                // 来源2：前一天无持仓，今天买入开多仓
                dp[i][j][1] = Math.max(dp[i][j][1], dp[i-1][j][0] - prices[i]);

                // ========== 状态2：第i天做空仓（做空） ==========
                // 来源1：前一天已做空仓，不操作
                dp[i][j][2] = Math.max(dp[i][j][2], dp[i-1][j][2]);
                // 来源2：前一天无持仓，今天卖出开空仓
                dp[i][j][2] = Math.max(dp[i][j][2], dp[i-1][j][0] + prices[i]);
            }
        }

        // 最终结果：最后一天所有交易次数下，无持仓状态的最大利润（落袋为安）
        long maxProfit = 0;
        for (int j = 0; j <= k; j++) {
            maxProfit = Math.max(maxProfit, dp[n-1][j][0]);
        }
        return maxProfit;
    }

4. 代码优化说明

官方题解

class lc3600_lc3699.lc3660.Solution {
    public long maximumProfit(int[] prices, int k) {
        long[][] f = new long[k + 2][3];
        for (int j = 1; j <= k + 1; j++) {
            f[j][1] = Long.MIN_VALUE / 2; // 防止溢出
        }
        f[0][0] = Long.MIN_VALUE / 2;
        for (int p : prices) {
            for (int j = k + 1; j > 0; j--) {
                f[j][0] = Math.max(f[j][0], Math.max(f[j][1] + p, f[j][2] - p));
                f[j][1] = Math.max(f[j][1], f[j - 1][0] - p);
                f[j][2] = Math.max(f[j][2], f[j - 1][0] + p);
            }
        }
        return f[k + 1][0];
    }
}

5. 复杂度分析

6. 总结