122.买卖股票 II

LeetCode 原题链接 题目

动态规划

dp 数组含义

题目允许完成多笔交易，但同一时间最多只能持有一只股票。也就是说，必须先卖出手里的股票，才能再次买入。

每天结束后，手里只有两种状态：

dp[i][0] // 第 i 天结束后，不持有股票时的最大利润
dp[i][1] // 第 i 天结束后，持有股票时的最大利润

这里的“第 i 天结束后”表示第 i 天的买入、卖出、什么都不做这些选择都已经考虑完了。

最终答案应该是不持有股票的最大利润：

dp[prices.length - 1][0]

因为最后如果还持有股票，说明这只股票还没有卖出，利润不会最大。

确定状态转移方程

第 i 天结束后不持有股票

dp[i][0] 有两种来源：

  1. 昨天就不持有股票，今天什么都不做：
dp[i - 1][0]
  1. 昨天持有股票，今天卖出：
dp[i - 1][1] + prices[i]

所以：

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

第 i 天结束后持有股票

dp[i][1] 也有两种来源：

  1. 昨天就持有股票，今天继续持有：
dp[i - 1][1]
  1. 昨天不持有股票，今天买入：
dp[i - 1][0] - prices[i]

本题允许多次交易，所以今天买入时，可以继承昨天不持股状态下已经获得的利润。

所以：

dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

这也是本题和“121. 买卖股票的最佳时机”的核心区别：

  • 121 只能交易一次，买入时写 -prices[i]。
  • 122 可以交易多次，买入时写 dp[i - 1][0] - prices[i]。

dp 数组如何初始化

第 0 天只有一个价格 prices[0]。

dp[0][0] = 0;
dp[0][1] = -prices[0];

含义：

  • dp[0][0] = 0：第 0 天结束后不持有股票，说明什么都不做，利润是 0。
  • dp[0][1] = -prices[0]：第 0 天结束后持有股票，说明在第 0 天买入了股票，利润是负的买入价格。

如果 prices 为空，没有价格可以交易，直接返回 0。

确定遍历顺序

dp[i][0] 依赖：

dp[i - 1][0]
dp[i - 1][1]

dp[i][1] 也依赖：

dp[i - 1][0]
dp[i - 1][1]

当前第 i 天的状态都从前一天转移而来，所以从前往后遍历价格数组：

for (let i = 1; i < prices.length; i++) {
  // 更新 dp[i][0] 和 dp[i][1]
}

举例推导

以 prices = [7, 1, 5, 3, 6, 4] 为例。

初始化：

第 0 天，价格 7
dp[0] = [0, -7]

完整 dp 数组变化如下：

下标 i     价格     dp[i][0] 不持股     dp[i][1] 持股
0          7        0                  -7
1          1        0                  -1
2          5        4                  -1
3          3        4                   1
4          6        7                   1
5          4        7                   3

解释几个关键位置：

  • 第 1 天价格为 1，买入更划算，所以 dp[1][1] = -1。
  • 第 2 天价格为 5，卖出可以获得利润 4，所以 dp[2][0] = 4。
  • 第 3 天价格为 3，可以用之前赚到的 4 再买入，利润变成 4 - 3 = 1，所以 dp[3][1] = 1。
  • 第 4 天价格为 6，卖出后利润变成 1 + 6 = 7，所以 dp[4][0] = 7。

最终答案：

dp[5][0] = 7

也就是先在 1 买入、5 卖出，再在 3 买入、6 卖出，最大利润为 4 + 3 = 7。

代码实现

var maxProfit = function (prices) {
  if (prices.length === 0) return 0;

  const dp = new Array(prices.length).fill(0).map(() => [0, 0]);

  dp[0][0] = 0;
  dp[0][1] = -prices[0];

  for (let i = 1; i < prices.length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  }

  return dp[prices.length - 1][0];
};

复杂度分析

  • 时间复杂度：O(n)，只遍历一次价格数组。
  • 空间复杂度：O(n)，使用 dp 数组保存每天的两个状态。

空间优化

因为第 i 天只依赖第 i - 1 天，所以可以用两个变量保存状态。

var maxProfit = function (prices) {
  if (prices.length === 0) return 0;

  let noStock = 0;
  let hasStock = -prices[0];

  for (let i = 1; i < prices.length; i++) {
    const prevNoStock = noStock;
    noStock = Math.max(noStock, hasStock + prices[i]);
    hasStock = Math.max(hasStock, prevNoStock - prices[i]);
  }

  return noStock;
};

贪心算法

解题思路

本题允许完成多笔交易，并且没有手续费、冷冻期等额外限制。因此，只要后一天的价格比前一天高，就可以收集这两天之间的上涨利润：

prices[i] - prices[i - 1]

遍历价格数组，把所有大于 0 的相邻价格差累加起来，就是能够获得的最大利润。

为什么只收集正利润

假设股票价格连续上涨：

[1, 3, 6]

在价格为 1 时买入、价格为 6 时卖出，利润为：

6 - 1 = 5

也可以把这段上涨拆成相邻两天的利润：

(3 - 1) + (6 - 3) = 5

两种计算方式的结果完全相同。因此，一段连续上涨行情可以被拆成每一天的正利润，拆分后不会少赚。

如果相邻两天的价格下降，例如：

3 - 5 = -2

这段交易会产生亏损，可以直接跳过。由于交易次数不限，后面再次上涨时仍然可以买入，不会影响后续交易。

所以贪心策略是：

只收集所有相邻两天之间的正利润，忽略负利润。

举例推导

以 prices = [7, 1, 5, 3, 6, 4] 为例：

相邻价格       价格差       是否计入
7 → 1          -6           否
1 → 5           4           是
5 → 3          -2           否
3 → 6           3           是
6 → 4          -2           否

最终利润为：

4 + 3 = 7

对应的实际交易是：

价格 1 时买入，价格 5 时卖出，利润为 4；
价格 3 时买入，价格 6 时卖出，利润为 3。

代码实现

var maxProfit = function (prices) {
  let profit = 0;

  for (let i = 1; i < prices.length; i++) {
    const dailyProfit = prices[i] - prices[i - 1];

    if (dailyProfit > 0) {
      profit += dailyProfit;
    }
  }

  return profit;
};

也可以使用 Math.max 简化判断：

var maxProfit = function (prices) {
  let profit = 0;

  for (let i = 1; i < prices.length; i++) {
    profit += Math.max(prices[i] - prices[i - 1], 0);
  }

  return profit;
};

与第 121 题的区别

  • 第 121 题最多只能完成一笔交易，所以需要维护历史最低价格，寻找最大的一段上涨利润。
  • 第 122 题可以完成多笔交易，所以可以收集所有相邻两天之间的正利润。

这个贪心策略成立的前提是：交易次数不限，并且没有手续费、冷冻期等额外限制。如果题目加入这些条件，就不能直接累加所有正价格差。

复杂度分析

  • 时间复杂度：O(n)，只遍历一次价格数组。
  • 空间复杂度：O(1)，只使用一个变量累计利润。