Leetcode 188 买卖股票的最佳时机 Ⅳ

java solution

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(n == 1) return 0;
        if(k >= n/2) {
            return maxProfitUnlimited(prices);
        }
        //创建dp数组
        int[][] dp = new int[k + 1][n];

        for(int i = 1; i <= k; i++) {
            int maxDiff = -prices[0]; //最开始dp[0][j] = 0, 所以 maxDiff 初始值为 -prices[0]
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], prices[j] + maxDiff);
                maxDiff = Math.max(maxDiff, dp[i - 1][j] - prices[j]);
//dp[i][j] = Math.max(dp[i][j - 1], \sigma 1-m (prices[j] - prices[m] + dp[i - 1][m]))
//本来dp[i][j]是这个状态转移方程，为了优化计算，我们把prices[j]提出来,剩余部分定义为maxDiff
            }
        }

        return dp[k][n - 1];
    }

    private int maxProfitUnlimited(int[] prices) {
        int profit = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

太好了！理解 maxDiff 是彻底掌握这道股票交易类 DP 题目的关键之一。下面我会从 直观解释 + 数学表达式 + 举例 + 图解思维 全方位帮你搞懂它。

🔍 1. 什么是 maxDiff？

maxDiff 是一种“提前算好买入时机的优化变量”。

它表示在进行第 i 次交易之前，在第 j 天卖出时，如果我们曾经在第 m 天买入，那么最大能获得的利润是多少？

核心公式是：

$$\text{maxDiff}=\underset{0\le m<j}{\max }(dp[i-1][m]-prices[m])$$

📌 翻译成人话：

maxDiff 记录的是：
“如果我在第 j 天卖出，那么我应该回头找一个【历史最划算的买入时机（第 m 天）】，
并且这个买入时机要考虑：我最多只能完成 i-1 次交易，买之前还有多少本金/利润。”

🧠 2. 为什么要这样设计？（解决了什么问题）

原始的动态规划状态转移是这样的：

$$dp[i][j]=\underset{0\le m<j}{\max }(dp[i-1][m]+prices[j]-prices[m])$$

我们要在第 j 天卖出，那么就要枚举所有 m < j 的买入日，非常慢，时间复杂度是 (O(k \cdot n^2))。

👉 但注意观察公式中 dp[i-1][m] + prices[j] - prices[m]，我们可以把它拆成两部分：

$$dp[i][j]=\max (prices[j]+\underset{0\le m<j}{\max }(dp[i-1][m]-prices[m]))$$

✅ 这时我们只需要维护一个变量 maxDiff，它在 j 遍历过程中不断更新，这样就避免了一个内层循环，将复杂度降为 $O(k\cdot n)$。

📈 3. 举个例子说明

prices = [3, 2, 6, 5, 0, 3]
k = 2

假设现在正在处理：

• 第 i = 2 次交易
• 当前是第 j = 5 天（价格 = 3）

我们要计算：

dp[2][5] = Math.max(dp[2][4], prices[5] + maxDiff)

那 maxDiff 就是：

$$\max (dp[1][0]-prices[0],dp[1][1]-prices[1],\dots ,dp[1][4]-prices[4])$$

也就是说：

如果我现在要在第6天（index=5）卖出，那么我曾经在哪一天（m=0到4）买入最划算？

这“划算”的意思是：当时能留下最多的利润给这次交易用。

🔁 4. 为什么每次都更新 maxDiff？

因为：

maxDiff = Math.max(maxDiff, dp[i - 1][j] - prices[j])

我们在遍历每一天 j 时，不断尝试把这一天作为潜在买入点（用于未来某一天的卖出），这样后面的天数可以用 maxDiff 快速计算。

就像在走路时，手里一直带着一个“最佳买点”的记忆，随时准备在未来卖出的时候参考它。

🧊 小结回顾：

📌 如果你喜欢类比

可以把 maxDiff 想象成：

一位随身带计算器的股市助手，他在你每卖出一只股票时，都能立即告诉你：「我们过去所有历史里，哪一次买入最划算，加上你的本钱，可以赚最多！」

为什么k >= n/2时，可以认为是无限次交易？

这个问题问得非常好！🌟
理解了这个，就掌握了为什么 Leetcode 股票题中经常会特判 k >= n/2 的情况，并用贪心法处理。

💡 问题回顾：

我们最多只能做 k 次交易（1次交易 = 1次买 + 1次卖），但如果 k >= n/2，
为什么就可以认为是“可以进行无限次交易”呢？

📌 回答核心：

✅ 因为一个交易周期（买+卖）至少需要 2 天

• 第 i 天买入，最早第 i+1 天卖出
• 所以：
  • 最多一天买、一天卖，2 天完成一次交易
  • 如果有 n 天时间，最多也只能做 n/2 次交易

📈 举个例子（直观理解）：

假设 prices.length = 6，也就是有 6 天：

prices = [3, 2, 6, 5, 0, 3]

那么：

• 最多你能买入/卖出几次？
  • 最理想的情况是：每隔一天交易一次
    • 第1天买，第2天卖（第1次）
    • 第3天买，第4天卖（第2次）
    • 第5天买，第6天卖（第3次）
• 所以最多可以进行 3 = 6 / 2 次交易

👉 也就是说，不管你 k 有多大，6 天时间最多只能完成 3 次完整的交易

🤖 所以当 k >= n/2：

这时候 交易次数限制形同虚设，因为就算你允许再多交易，也没有足够的天数去执行。

你就可以把它看成是没有交易次数限制，也就是 可以无限次交易。

🚀 如何解决无限次交易的问题？

直接使用贪心策略：

for (int i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
        profit += prices[i] - prices[i - 1]; // 涨了就买卖一把
    }
}

即：所有上涨的波段都吃掉，每段赚差价

✅ 总结表：

📌 类比理解：

可以把“交易次数 k”想成“子弹数”，而“n 天”是“靶子数”

• 如果你子弹比靶子还多，你当然可以每次都射击，不用担心次数
• 所以：k >= n/2 时，就不再需要动态规划了，直接贪心扫一遍即可。

如果你还想看具体数据对比（比如动态规划 vs 贪心的输出对比），我也可以补充示例～