122.买卖股票 II

`dp` 数组含义

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

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

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

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

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

dp[prices.length - 1][0]

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

确定状态转移方程

第`i` 天结束后不持有股票

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

昨天就不持有股票，今天什么都不做：

dp[i - 1][0]

昨天持有股票，今天卖出：

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] 也有两种来源：

昨天就持有股票，今天继续持有：

dp[i - 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]
}

举例打印`dp` 数组

以 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;
};

ON THIS PAGE

#122.买卖股票 II

#dp 数组含义

#确定状态转移方程

#第i 天结束后不持有股票

#第i 天结束后持有股票

#dp 数组如何初始化

#确定遍历顺序

#举例打印dp 数组

#代码实现

#复杂度分析

#空间优化