LC123. 买卖股票的最佳时机 III

题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。 示例 2： 输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 示例 3： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。 示例 4： 输入：prices = [1] 输出：0 提示： 1 <= prices.length <= 10(5) 0 <= prices[i] <= 10(5)

题目解析

好的，没问题。我是 AlgoMooc 的算法老师，咱们今天就用最轻松、最白话的方式，把这个“买卖股票”的难题给它拆解明白。别怕，跟着我一步步来，你肯定能学会。

---

题目在说什么

想象一下，你是一个股票交易员，每天盯着股票价格。题目给了你一个数组，比如 [3,3,5,0,0,3,1,4]，里面的每个数字就是当天股票的价格。

你的任务很简单：通过最多两次买卖，赚到最多的钱。

规则也很简单： 1. 最多两次买卖：你可以一次都不买，可以只买卖一次，也可以买卖两次。但不能超过两次。 2. 不能同时持有：你手里最多只能有一只股票。想买第二只，必须先把第一只卖掉。也就是“先卖后买”。

比如示例1，价格是 [3,3,5,0,0,3,1,4]，最佳操作是：

• 第4天价格是0的时候买入，第6天价格是3的时候卖出，赚了3块。
• 然后第7天价格是1的时候再买入，第8天价格是4的时候卖出，又赚了3块。
• 总共赚了6块。

如果价格一直跌，比如 [7,6,4,3,1]，那就不买，利润为0。

所以，题目就是要你算出，在遵守这些规则下，最多能赚多少钱。

---

思路是怎么来的

新手看到这种题，最容易想到的是“我能不能在第i天买入，第j天卖出，然后第m天再买入，第n天再卖出...”，这样去穷举所有可能。但价格数组可能很长（最多10万天），穷举会慢到爆炸。

那计算机科学家是怎么想的呢？他们发明了一种叫“动态规划”的方法，核心思想就是：把一个大问题，拆成一系列有联系的小问题，然后从第一天开始，一步一步地，把每天的最优结果算出来，最后一天的结果就是答案。

为了让你更好理解，我们打个比方。

生活化的比喻：你是一个“机会猎人”

想象你是一个猎人，你的任务是去森林里打最多两只兔子。你有一个背包，最多只能装一只兔子（对应“不能同时持有”）。森林里有很多兔子（对应“价格波动”），你看到兔子可以抓（买入），也可以卖掉（卖出）。你的目标是，通过最多两次“抓和卖”的操作，赚到最多的钱。

现在，你站在第1天（森林入口），你面临几个选择，每个选择都对应一个“状态”： 1. 状态A： 你手里没兔子，并且你还有2次抓兔子的机会。此时你的收益是0。 2. 状态B： 你手里没兔子，并且你还有1次抓兔子的机会。收益也是0。 3. 状态C： 你手里有一只兔子，并且你还有2次抓兔子的机会。因为你已经抓了一只，所以你的收益是负的（因为你花了钱买兔子），比如花了3块，收益就是-3。 4. 状态D： 你手里有一只兔子，并且你还有1次抓兔子的机会。收益也是负的。

你看，我们就把“猎人”的状态，用三个信息描述清楚了：

• 今天是第几天（i）
• 手里有没有兔子（b：0表示没有，1表示有）
• 还剩几次抓兔子的机会（k：0，1，2）

题目里，我们最多交易两次，所以k最大就是2。

动态规划怎么玩？

我们不用去管未来，只需要从第1天开始，每天更新一下上面这几种状态下的“最优收益”是多少。

比如，到了第2天，价格变了。猎人就可以选择：

• 如果昨天手里没兔子（状态A）： 今天可以继续观望（状态A不变），或者今天抓一只兔子（变成状态C）。
• 如果昨天手里有兔子（状态C）： 今天可以把兔子卖掉（变成状态A，并且赚了差价），或者继续持有（状态C不变）。

我们每天就做这个“选择”，并且只记录下每个状态下的最大收益。比如，状态A今天可能有两种方式达到：一种是昨天就是状态A然后没操作，另一种是昨天是状态C然后卖掉了兔子。我们选收益大的那个记录下来。

这样，我们就像玩游戏一样，一天一天地“走”下去，最后一天，我们看“手里没兔子，并且还剩2次机会”这个状态下的收益，就是答案。因为最后一天，手里没兔子才叫赚到钱了，而且我们最多有2次机会，这个状态包含了所有可能。

---

代码逐步拆解

现在，我们来看代码是怎么实现这个“猎人”思路的。代码里用了一个三维数组 dp[i][k][b] 来记录每天每个状态的最大收益。

• i：第几天（从0开始）。
• k：还剩几次交易机会（0，1，2）。注意：代码里把“买入”算作消耗一次机会。
• b：是否持有股票（0：不持有，1：持有）。

第一步：初始化（第0天）

int length = prices.length;
int[][][] dp = new int[length][3][2];

// 第0天，手里没股票，还剩0次机会 -> 收益0
dp[0][0][0] = 0;