LC122. 买卖股票的最佳时机 II（贪心解法）

题目描述

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 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。 提示： 1 <= prices.length <= 3 * 10(4) 0 <= prices[i] <= 10(4)

题目解析

题目在说什么

这道题是让我们模拟炒股。给你一串股票每天的价格，比如 [7,1,5,3,6,4]，你可以多次买卖（但必须先卖才能再买），目标是算出能赚到的最大总利润。

举个生活中的例子：你发现苹果价格每天在变，今天7元，明天1元，后天5元……你可以今天买明天卖，也可以等几天再卖。只要觉得未来价格会涨，就买入；觉得未来会跌，就卖出。题目允许你无限次交易，但每次只能持有一股（不能同时买多股）。

思路是怎么来的

想象你是一个水果贩子，每天盯着苹果价格。你的目标很简单：低买高卖，赚差价。但有一个关键点：你只能先买后卖，不能先卖后买（做空）。

那么，怎么才能赚最多钱呢？一个很直观的想法是：只要明天的价格比今天高，今天就买入，明天就卖出。这样每次赚一点，累积起来就是最大利润。比如 [1,2,3,4,5]，每天价格都在涨，那就第一天1元买，第二天2元卖，赚1元；第二天2元买，第三天3元卖，又赚1元……总共赚4元。这其实就是贪心思想：只赚正差价，不放过任何上涨机会。

但题目要求用动态规划（DP）来做。动态规划是一种“记住过去，规划未来”的方法。我们每天有两个状态：持有股票或不持有股票。比如今天收盘时，我手里有股票，那可能是昨天就有没卖，也可能是今天刚买的；我手里没股票，可能是昨天就没买，也可能是今天刚卖的。我们只需要每天记录这两种状态下能赚到的最多钱，然后一步步推导到最后一天。

为什么这样能行？因为每天的选择只和前一天有关：今天持有股票，要么是昨天持有今天没卖，要么是昨天不持有今天买入；今天不持有，要么是昨天不持有今天没买，要么是昨天持有今天卖出。这样我们就能用前一天的结果算出今天的，就像搭积木一样。

代码逐步拆解

我们来看参考代码，并把它拆成一步步理解。

1. 初始化

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

• dp[i][0] 表示第 i 天收盘时不持有股票能赚的最大钱数。
• dp[i][1] 表示第 i 天收盘时持有股票能赚的最大钱数。
• 注意：持有股票时，利润是负的，因为钱花出去了。比如第一天价格7元，买入后利润就是 -7元。

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

• 第0天（第一天）不持有：没买没卖，利润0。
• 第0天持有：买了股票，花了7元，利润 -7元。

2. 遍历每一天

从第1天开始，一直到第 length-1 天（最后一天），每天更新两个状态。

for (int i = 1; i < 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]);
}

第一行：今天不持有股票

• 有两种可能：

1. 昨天就不持有，今天也没买：利润就是 dp[i-1][0]。 2. 昨天持有，今天卖掉了：利润是 dp[i-1][1] + prices[i]（昨天持有时的利润，加上今天卖出得到的钱）。

• 取两者中较大的，就是今天不持有的最佳利润。

第二行：今天持有股票

• 有两种可能：

1. 昨天就持有，今天没卖：利润就是 dp[i-1][1]。 2. 昨天不持有，今天买入：利润是 dp[i-1][0] - prices[i]（昨天不持有的利润，减去今天买入花的钱）。

• 取两者中较大的，就是今天持有的最佳利润。

3. 返回结果

return dp[length-1][0];

• 最后一天，我们肯定希望手里没有股票（因为股票没卖掉，利润只是账面上的，不算真赚），所以返回 dp[length-1][0]，即最后一天不持有股票的最大利润。

举个例子：prices = [7,1,5]

• 第0天：dp[0][0]=0，dp[0][1]=-7
• 第1天（价格1）：