LC309. 最佳买卖股票时机含冷冻期

题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

题目解析

题目在说什么

这道题是让我们在股票市场里赚钱，但有两个规矩：

1. 可以买卖很多次，但必须先卖掉才能再买（不能同时持有两支股票）。 2. 卖完股票后，第二天不能买，必须休息一天（这就是“冷冻期”）。

比如给的例子 [1,2,3,0,2]：

• 第一天价格1，买入。
• 第二天价格2，卖出，赚1块。但第二天卖完，第三天就不能买。
• 第三天价格3，是冷冻期，不能操作。
• 第四天价格0，可以买入。
• 第五天价格2，卖出，赚2块。

总共赚3块。

题目要我们算出：给定每天的价格，最多能赚多少钱。

思路是怎么来的

想象你是一个股票交易员，每天收盘后都要做总结。你只关心两件事：

1. 今天收盘时手里有没有股票（持有还是不持有）。 2. 今天赚了多少钱（最大利润）。

每天你都有选择：可以买卖，也可以什么都不做。但因为有冷冻期，卖完股票后第二天不能买，所以决策时要考虑“昨天卖了没”。

我们用一个表格来记录每天的最佳情况：

• 第0天：手里没股票，利润0；或者买了股票，利润是负的（花了钱）。
• 第1天：看前一天的状态，决定今天怎么做。
• 第2天：看前一天和前天（因为冷冻期需要看两天前的状态）。

这种“每天记录两种状态，从过去推导未来”的方法，就是动态规划。就像下棋，每一步都基于上一步的结果，选出最好的走法。

代码逐步拆解

我们来看参考代码，一步步解释。

1. 准备阶段

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

• dp[i][0]：第 i 天收盘时，不持有股票的最大利润。
• dp[i][1]：第 i 天收盘时，持有股票的最大利润。

2. 初始化（第0天）

dp[0][0] = 0;          // 没买，利润0
dp[0][1] = -prices[0]; // 买了，花了钱，利润是负数

第0天只有两种可能：什么都不做（利润0），或者买入（利润 - 价格）。

3. 从第1天开始循环

for (int i = 1; i < length; i++) {

每一天我们都要更新两种状态。

今天不持有股票

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

• 情况A：昨天就不持有，今天继续不持有（没操作）。利润 = dp[i-1][0]。
• 情况B：昨天持有，今天卖出。利润 = dp[i-1][1] + prices[i]（昨天持有时的利润 + 今天卖出的收入）。

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

今天持有股票

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

• 情况A：昨天就持有，今天继续持有（没操作）。利润 = dp[i-1][1]。