线性动态规划：买卖股票的最佳时机（含多次交易限制与手续费）

题目描述

给你一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。同时给你一个整数 fee 表示交易股票时的手续费。你可以无限次地完成交易（即多次买卖一支股票），但你不能在一天内同时进行买入和卖出操作（即必须先买入，再卖出，且每次卖出后需支付手续费）。请你计算并返回你能够获得的最大利润。

示例：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：在第 1 天买入（价格 = 1），第 4 天卖出（价格 = 8），利润 = 8 - 1 - 2 = 5；然后在第 5 天买入（价格 = 4），第 6 天卖出（价格 = 9），利润 = 9 - 4 - 2 = 3。总利润 = 5 + 3 = 8。

解题思路

这是一个经典的动态规划问题，核心在于每天结束时我们有两种状态：持有股票或未持有股票。我们需要分别计算这两种状态下的最大利润。

状态定义

• dp[i][0]：表示第 i 天结束时，不持有股票（即卖出或一直未买）的最大利润。
• dp[i][1]：表示第 i 天结束时，持有股票（即买入后还未卖出）的最大利润。

状态转移方程

1. 第 i 天不持有股票 (dp[i][0])：

   • 可能来自前一天也不持有股票：dp[i-1][0]
   • 或者前一天持有股票，但今天卖出（需支付手续费）：dp[i-1][1] + prices[i] - fee
   • 取两者较大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)

2. 第 i 天持有股票 (dp[i][1])：

   • 可能来自前一天也持有股票：dp[i-1][1]
   • 或者前一天不持有股票，但今天买入：dp[i-1][0] - prices[i]
   • 取两者较大值：dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

初始状态

• 第 0 天（即开始时）：
  • dp[0][0] = 0（未买入，利润为 0）
  • dp[0][1] = -prices[0]（买入，利润为负的买入价）

最终答案

最后一天不持有股票时利润最大，即 dp[n-1][0]。

逐步计算示例

以 prices = [1, 3, 2, 8, 4, 9], fee = 2 为例：

1. 初始化：

   • dp[0][0] = 0
   • dp[0][1] = -1

2. 第 1 天 (i=1, price=3)：

   • dp[1][0] = max(0, -1 + 3 - 2) = max(0, 0) = 0
   • dp[1][1] = max(-1, 0 - 3) = max(-1, -3) = -1

3. 第 2 天 (i=2, price=2)：

   • dp[2][0] = max(0, -1 + 2 - 2) = max(0, -1) = 0
   • dp[2][1] = max(-1, 0 - 2) = max(-1, -2) = -1

4. 第 3 天 (i=3, price=8)：

   • dp[3][0] = max(0, -1 + 8 - 2) = max(0, 5) = 5 ← 第一次卖出，利润 5
   • dp[3][1] = max(-1, 0 - 8) = max(-1, -8) = -1

5. 第 4 天 (i=4, price=4)：

   • dp[4][0] = max(5, -1 + 4 - 2) = max(5, 1) = 5
   • dp[4][1] = max(-1, 5 - 4) = max(-1, 1) = 1 ← 第二次买入（利润 5 - 4 = 1）

6. 第 5 天 (i=5, price=9)：

   • dp[5][0] = max(5, 1 + 9 - 2) = max(5, 8) = 8 ← 第二次卖出，总利润 8
   • dp[5][1] = max(1, 5 - 9) = max(1, -4) = 1

最终答案：dp[5][0] = 8。

空间优化

由于 dp[i] 只依赖于 dp[i-1]，我们可以用两个变量代替二维数组：

• cash：表示当前不持有股票的最大利润（对应 dp[i][0]）
• hold：表示当前持有股票的最大利润（对应 dp[i][1]）

更新过程：

cash = 0
hold = -prices[0]
for i in range(1, len(prices)):
    cash = max(cash, hold + prices[i] - fee)
    hold = max(hold, cash - prices[i])
return cash

关键点

• 手续费在卖出时扣除，这影响了卖出决策。
• 状态转移方程清晰地刻画了“买入”和“卖出”两个动作。
• 初始持有状态为负，表示成本支出。

通过上述步骤，我们可以高效地计算出在包含手续费的情况下，多次交易股票所能获得的最大利润。