本文深入探讨 LeetCode 122：买卖股票的最佳时机 II，阐述其与 LeetCode 121 的主要区别，并分析了三种不同的解法：贪心算法、动态规划 (DP) 以及优化后的 DP。

LeetCode 122: 买卖股票的最佳时机 II

问题描述:

给定一个整数数组 prices，其中 prices[i] 是某支股票在第 i 天的价格。你可以决定在每一天买入和/或卖出股票。任何时候你最多只能持有一股股票。但是，你可以在同一天买入并立即卖出。找到并返回你能获得的最大利润。

与 LeetCode 121 的主要区别:

• LeetCode 121 (买卖股票的最佳时机): 最多允许 一次交易（一次买入和一次卖出）。目标是找到产生最大利润的单次交易。
• LeetCode 122 (买卖股票的最佳时机 II): 允许 多次交易。只要不同时持有超过一股股票，你可以买卖任意次数。目标是最大化所有交易的总利润。

这个区别从根本上改变了策略。在 121 中，我们寻找最低的买入价格和随后的最高卖出价格。而在 122 中，我们可以抓住价格上涨的每一个机会。

LeetCode 122 解法分析

以下是提供的三种解法的分析：

解法 1: 贪心算法

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2) return 0;
        int maxProfit = 0;
        for(int i = 1; i < n; i++){
            // 如果今天的价格高于昨天，将差价计入利润
            if(prices[i] > prices[i-1]){
                maxProfit += prices[i] - prices[i-1];
            }
        }
        return maxProfit;
    }
}

• 逻辑: 该方法从第二天开始遍历价格数组。如果当天的价格 (prices[i]) 高于前一天的价格 (prices[i-1])，这意味着在第 i-1 天买入并在第 i 天卖出可以获利。算法简单地将这个潜在利润 (prices[i] - prices[i-1]) 加入总利润 maxProfit。
• 为何有效: 它捕捉了所有的上涨趋势。考虑序列 [1, 5, 3, 6]：
  • 第 1 天到第 2 天：prices[1] > prices[0] (5 > 1)。增加 5 - 1 = 4。maxProfit = 4。
  • 第 2 天到第 3 天：prices[2] < prices[1] (3 < 5)。无操作。
  • 第 3 天到第 4 天：prices[3] > prices[2] (6 > 3)。增加 6 - 3 = 3。maxProfit = 4 + 3 = 7。 这相当于在 1 买入，在 5 卖出 (利润 4)，然后在 3 买入，在 6 卖出 (利润 3)。贪心算法通过累加所有连续的价格上涨，正确地计算了所有可能的利润。它通过累加所有正的日间收益，隐式地处理了多次买卖。
• 效率: 时间复杂度 O(N)，空间复杂度 O(1)。非常高效。

解法 2: 动态规划 (DP) - 使用二维数组

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2) return 0;
        // dp[i][0]: 第 i 天结束时，不持有股票的最大利润
        // dp[i][1]: 第 i 天结束时，持有一股股票的最大利润
        int[][] dp = new int[n][2];

        // 基础情况: 第 0 天
        dp[0][0] = 0;         // 不持有股票，没有利润
        dp[0][1] = -prices[0]; // 第 0 天买入股票

        for(int i = 1; i < n; i++){
            // 今天不持有股票的最大利润:
            // 1. 昨天就不持有股票，今天休息 (dp[i-1][0])
            // 2. 昨天持有股票，今天卖出 (dp[i-1][1] + prices[i])
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);

            // 今天持有股票的最大利润:
            // 1. 昨天就持有股票，今天继续持有 (dp[i-1][1])
            // 2. 昨天不持有股票，今天买入 (dp[i-1][0] - prices[i])
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        // 最终答案是最后一天不持有股票的最大利润
        return dp[n-1][0];
    }
}

• 逻辑: 使用 DP 来追踪在每天结束时，考虑持有股票或不持有股票两种状态下能达到的最大利润。
• 状态定义:
  • dp[i][0]: 到第 i 天为止，当天结束时不持有股票的最大利润。
  • dp[i][1]: 到第 i 天为止，当天结束时持有一股股票的最大利润。
• 状态转移: 状态转移方程根据第 i-1 天的可能状态计算第 i 天的最大利润：
  • 第 i 天不持有股票 (dp[i][0]): 你可能是在第 i-1 天就不持有股票并且今天休息 (dp[i-1][0])，或者在第 i-1 天持有股票并在今天卖出 (dp[i-1][1] + prices[i])。取两者最大值。
  • 第 i 天持有股票 (dp[i][1]): 你可能是在第 i-1 天就持有股票并且今天继续持有 (dp[i-1][1])，或者在第 i-1 天不持有股票并在今天买入 (dp[i-1][0] - prices[i])。取两者最大值。
• 基础情况: 第 0 天，如果不持有股票，利润为 0。如果买入股票，利润为 -prices[0] (代表成本)。
• 结果: 最终答案是 dp[n-1][0]，因为在最后一天，持有现金（不持有股票）总是优于或等于持有股票（因为卖出总是最大化利润的一个选项）。
• 效率: 时间复杂度 O(N)，空间复杂度 O(N) 用于 dp 数组。

解法 3: 优化后的动态规划 (常数空间)

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2) return 0;

        // 代表 dp[i-1][0] (前一天不持有股票的最大利润)
        int noStock = 0;
        // 代表 dp[i-1][1] (前一天持有股票的最大利润)
        int haveStock = -prices[0];

        for(int i = 1; i < n; i++){
            // 计算当天不持有股票的最大利润
            // 等价于 dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            int currentNoStock = Math.max(noStock, haveStock + prices[i]);

            // 计算当天持有股票的最大利润
            // 等价于 dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
            int currentHaveStock = Math.max(haveStock, noStock - prices[i]);

            // 更新状态以供下一次迭代 (i+1) 使用
            noStock = currentNoStock;
            haveStock = currentHaveStock;
        }
        // 最终答案是最后一天不持有股票的最大利润
        return noStock;
    }
}

• 逻辑: 这个解法观察到第 i 天的 DP 计算只依赖于第 i-1 天的结果。因此，我们不需要整个 dp 数组，只需要存储 dp[i-1][0] 和 dp[i-1][1] 的值。
• 优化: 使用两个变量 noStock 和 haveStock 来分别代表前一天不持有股票和持有股票的最大利润。在循环内部，使用前一天的值计算当天的最大利润 (currentNoStock, currentHaveStock)。然后，将 noStock 和 haveStock 更新为这些新计算的值，用于下一次迭代。
• 效率: 时间复杂度 O(N)，空间复杂度 O(1)。这种方法保持了 DP 的逻辑，但优化了空间复杂度。

DP 思考过程与示例

我们是如何想到 DP 解法的？

1. 识别最优子结构和重叠子问题: 到第 i 天的最大利润取决于到第 i-1 天的最大利润以及在第 i 天采取的操作。这表明存在最优子结构。第 i-1 天的状态（是否持有股票）会影响未来的多个决策，这表明存在重叠子问题。这都指向了动态规划。
2. 定义状态: 在每个步骤（第 i 天）需要携带哪些信息才能做出未来的最优决策？我们需要知道到目前为止获得的最大利润，以及我们当前是否持有股票，因为这决定了我们接下来是买入还是卖出。这引出了两个状态：
   • dp[i][0]: 到第 i 天结束时不持有股票的最大利润。
   • dp[i][1]: 到第 i 天结束时持有股票的最大利润。
3. 构建状态转移方程: 如何从第 i-1 天的状态到达第 i 天的每个状态？
   • 到达 dp[i][0] (不持有股票):
     • 从 dp[i-1][0] (昨天不持有): 今天休息。利润保持 dp[i-1][0]。
     • 从 dp[i-1][1] (昨天持有): 今天卖出。利润变为 dp[i-1][1] + prices[i]。
     • 取最大值: dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])。
   • 到达 dp[i][1] (持有股票):
     • 从 dp[i-1][1] (昨天持有): 今天继续持有。利润保持 dp[i-1][1]。
     • 从 dp[i-1][0] (昨天不持有): 今天买入。利润变为 dp[i-1][0] - prices[i]。
     • 取最大值: dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])。
4. 定义基础情况: 第 0 天，dp[0][0] = 0 (开始时不持有股票，无利润)，dp[0][1] = -prices[0] (开始时买入股票)。
5. 确定最终答案: 在最后一天 (n-1)，我们想要最大可能的利润。如果 prices[n-1] 是正的，卖出总是比持有更好或相等。因此，最终答案是 dp[n-1][0]。

DP 表格示例

使用 prices = [7, 1, 5, 3, 6, 4]

结果: 最大利润为 dp[5][0] = 7。

结论

LeetCode 122 与 121 的不同之处在于允许无限次交易。这为简单的贪心方法打开了大门，该方法累加所有正的价格差。或者，可以通过考虑每天的状态（是否持有股票）来构建更通用的动态规划方法，然后可以将其优化为常数空间复杂度。虽然贪心解法对于这个特定问题简洁高效，但理解 DP 方法提供了一个强大的框架，适用于许多相关的股票交易问题。