线性动态规划：买卖股票的最佳时机含冷冻期 题目描述 给定一个整数数组 prices ，其中第 i 个元素代表了某支股票第 i 天的价格。请你设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票），但需要遵守以下规则： 在再次购买股票之前，你必须卖出你之前持有的股票。 卖出股票后，你无法在第二天（即冷冻期）买入股票。 解题过程 这个问题是股票买卖系列问题中一个经典的线性动态规划问题。关键在于如何定义状态，以及状态之间如何转移。由于存在冷冻期，我们需要更细致地区分持股状态。 步骤 1：定义状态 我们需要通过状态来记录每一天结束时，我们所处的不同情况。这里定义三个状态： dp[i][0] ：表示在第 i 天结束时， 持有 一支股票所能获得的最大累计利润。 dp[i][1] ：表示在第 i 天结束时， 不持有 股票，并且处于 冷冻期 （即当天卖出了股票）所能获得的最大累计利润。 dp[i][2] ：表示在第 i 天结束时， 不持有 股票，并且 不处于冷冻期 （即当天没有进行任何操作，或者冷冻期已过）所能获得的最大累计利润。 步骤 2：确定初始状态 在第一天（ i = 0 ）： dp[0][0] ：要持有股票，只能是在第一天买入。利润为 -prices[0] （因为支出了 prices[0] ）。 dp[0][1] ：第一天不可能卖出股票，所以这个状态不合法。通常我们将其初始化为一个很小的值（比如 -10^9 ）或者 0 （因为卖出操作本身不贡献利润，但结合规则，第一天无法达到此状态，这里我们初始化为 0 在后续转移中不会影响结果，因为 dp[0][1] 不会用于第一天的转移）。 dp[0][2] ：第一天不持有股票且不处于冷冻期（即什么都没做），利润为 0 。 为了逻辑清晰，我们通常这样初始化： dp[0][0] = -prices[0] dp[0][1] = 0 (或者一个很小的负数，但设为0在本题逻辑下是安全的) dp[0][2] = 0 步骤 3：建立状态转移方程 现在我们考虑第 i 天（ i >= 1 ）的状态如何从前一天的状态转移而来。 对于 dp[i][0] （第 i 天持有股票） ： 情况 A：我在第 i-1 天就已经持有这支股票，今天只是继续持有，没有操作。那么利润和前一天持有状态一样： dp[i-1][0] 。 情况 B：我在第 i 天 买入 了这支股票。那么，根据规则，我必须在买入前一天（第 i-1 天）不持有股票且 不处于冷冻期 （因为冷冻期禁止买入）。所以前一天的状态必须是 dp[i-1][2] 。买入后的利润是 dp[i-1][2] - prices[i] （前一天不持股非冷冻期的利润减去今天的买入成本）。 第 i 天持有股票的最大利润，就是这两种情况的最大值： dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) 对于 dp[i][1] （第 i 天不持股，且处于冷冻期） ： 要达到这个状态， 唯一 的可能性是：我在第 i 天 卖出了 股票。 既然卖出了股票，那么在第 i-1 天结束时，我 必须持有 股票。卖出的利润是前一天持有股票的利润加上今天卖出的收入： dp[i-1][0] + prices[i] 。 所以转移方程为： dp[i][1] = dp[i-1][0] + prices[i] 对于 dp[i][2] （第 i 天不持股，且不处于冷冻期） ： 这个状态表示我今天没有任何操作。那么，我前一天（第 i-1 天）结束时可以是什么状态呢？ 情况 A：前一天不持股且处于冷冻期（状态 [i-1][1] ）。过了一天，冷冻期结束，今天我就变成了不持股且不处于冷冻期。 情况 B：前一天不持股且不处于冷冻期（状态 [i-1][2] ）。今天继续不操作，状态不变。 第 i 天不持股非冷冻期的最大利润，是这两种情况的最大值： dp[i][2] = max(dp[i-1][1], dp[i-1][2]) 步骤 4：确定最终答案 我们考虑的是最后一天（ i = n-1 ）结束时的情况。在最后一天，持有股票（ dp[n-1][0] ）显然不是最优的，因为卖掉才能获得现金利润。 最优利润应该出现在最后一天 不持有股票 的状态中，即 dp[n-1][1] （当天卖出）和 dp[n-1][2] （早已卖出或一直未买入）中的最大值。 所以最终答案是： max(dp[n-1][1], dp[n-1][2]) 步骤 5：举例说明 假设 prices = [1, 2, 3, 0, 2] 。 初始化： dp[0][0] = -1 (买入价格1的股票) dp[0][1] = 0 dp[0][2] = 0 第 1 天 (i=1, price=2)： dp[1][0] = max(dp[0][0], dp[0][2] - 2) = max(-1, 0-2) = max(-1, -2) = -1 (继续持有第0天买的股票比今天买入更划算) dp[1][1] = dp[0][0] + 2 = -1 + 2 = 1 (卖出第0天买的股票，获利1) dp[1][2] = max(dp[0][1], dp[0][2]) = max(0, 0) = 0 (第0天没有冷冻期状态，所以是不持股非冷冻期) 第 2 天 (i=2, price=3)： dp[2][0] = max(dp[1][0], dp[1][2] - 3) = max(-1, 0-3) = max(-1, -3) = -1 (继续持有) dp[2][1] = dp[1][0] + 3 = -1 + 3 = 2 (卖出，获利2) dp[2][2] = max(dp[1][1], dp[1][2]) = max(1, 0) = 1 (从第1天的冷冻期状态 [1][1] 转来) 第 3 天 (i=3, price=0)： dp[3][0] = max(dp[2][0], dp[2][2] - 0) = max(-1, 1-0) = max(-1, 1) = 1 (今天买入，成本为0，基于第2天的非冷冻期状态 [2][2]=1 ，所以利润是1) dp[3][1] = dp[2][0] + 0 = -1 + 0 = -1 (卖出之前-1成本的股票，亏本) dp[3][2] = max(dp[2][1], dp[2][2]) = max(2, 1) = 2 (从第2天的卖出状态 [2][1]=2 或非冷冻期状态 [2][2]=1 转来，取最大值2) 第 4 天 (i=4, price=2)： dp[4][0] = max(dp[3][0], dp[3][2] - 2) = max(1, 2-2) = max(1, 0) = 1 (继续持有第3天买的股票) dp[4][1] = dp[3][0] + 2 = 1 + 2 = 3 (卖出第3天买的股票，获利3。这是关键操作：第3天价格0买入，第4天价格2卖出) dp[4][2] = max(dp[3][1], dp[3][2]) = max(-1, 2) = 2 最终答案： max(dp[4][1], dp[4][2]) = max(3, 2) = 3 。 这个结果对应的操作是：第0天买入(1)，第1天卖出(2)，获利1。经过第2天（冷冻期，无法买入），第3天买入(0)，第4天卖出(2)，获利2。总利润为 1 + 2 = 3。 通过这个循序渐进的步骤，我们清晰地解决了“买卖股票的最佳时机含冷冻期”这个线性动态规划问题。