121.买卖股票的最佳时机

`dp` 数组含义

题目要求最多只完成一笔交易，也就是只能买入一次、卖出一次。

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

dp[i][0] // 第 i 天结束后，不持有股票时的最大利润
dp[i][1] // 第 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]

今天第一次买入股票：

-prices[i]

本题最多只能完成一笔交易，所以买入之前的利润只能是 0，不能写成 dp[i - 1][0] - prices[i]。如果那样写，就表示可以把之前卖出的利润继续拿来买第二次股票了。

所以：

dp[i][1] = Math.max(dp[i - 1][1], -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][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        5                  -1
5          4        5                  -1

解释几个关键位置：

第 1 天价格为 1，此时买入更便宜，所以 dp[1][1] = -1。
第 2 天价格为 5，如果卖出，利润是 5 - 1 = 4，所以 dp[2][0] = 4。
第 4 天价格为 6，如果卖出，利润是 6 - 1 = 5，所以 dp[4][0] = 5。

最终答案：

dp[5][0] = 5

也就是在价格为 1 时买入，价格为 6 时卖出，最大利润为 5。

代码实现

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], -prices[i]);
  }

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

复杂度分析

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

空间优化

因为第 i 天只依赖第 i - 1 天，所以可以用两个变量代替整个 dp 数组。

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++) {
    noStock = Math.max(noStock, hasStock + prices[i]);
    hasStock = Math.max(hasStock, -prices[i]);
  }

  return noStock;
};

ON THIS PAGE

#121.买卖股票的最佳时机

#dp 数组含义

#确定状态转移方程

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

#第i 天结束后持有股票

#dp 数组如何初始化

#确定遍历顺序

#举例打印dp 数组

#代码实现

#复杂度分析

#空间优化