线性动态规划：买卖股票的最佳时机含手续费

题目描述：
给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格，以及一个整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润：
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润：((8 - 1) - 2) + ((9 - 4) - 2) = 8

解题过程：

步骤1：理解问题状态
这是一个典型的股票交易问题，我们需要考虑每天结束时可能处于的两种状态：

• 状态1：持有股票（手中有股票）
• 状态2：不持有股票（手中无股票）

对于每一天，我们需要决定是买入、卖出还是持有。

步骤2：定义DP数组
我们定义两个DP数组：

• hold[i]：表示第i天结束时持有股票时的最大利润
• cash[i]：表示第i天结束时不持有股票时的最大利润

步骤3：确定初始状态

• 第0天持有股票：hold[0] = -prices[0]（买入第一天的股票）
• 第0天不持有股票：cash[0] = 0（第一天不进行任何操作）

步骤4：状态转移方程
对于第i天（i ≥ 1）：

1. 持有股票的状态转移：

   • 可能1：前一天就持有股票，今天继续持有
   • 可能2：前一天不持有股票，今天买入股票
     hold[i] = max(hold[i-1], cash[i-1] - prices[i])

2. 不持有股票的状态转移：

   • 可能1：前一天就不持有股票，今天继续不持有
   • 可能2：前一天持有股票，今天卖出（需要支付手续费）
     cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee)

步骤5：逐步演算示例
以 prices = [1, 3, 2, 8, 4, 9], fee = 2 为例：

第0天：

• hold[0] = -1
• cash[0] = 0

第1天：

• hold[1] = max(hold[0], cash[0] - prices[1]) = max(-1, 0-3) = max(-1, -3) = -1
• cash[1] = max(cash[0], hold[0] + prices[1] - fee) = max(0, -1+3-2) = max(0, 0) = 0

第2天：

• hold[2] = max(hold[1], cash[1] - prices[2]) = max(-1, 0-2) = max(-1, -2) = -1
• cash[2] = max(cash[1], hold[1] + prices[2] - fee) = max(0, -1+2-2) = max(0, -1) = 0

第3天：

• hold[3] = max(hold[2], cash[2] - prices[3]) = max(-1, 0-8) = max(-1, -8) = -1
• cash[3] = max(cash[2], hold[2] + prices[3] - fee) = max(0, -1+8-2) = max(0, 5) = 5

第4天：

• hold[4] = max(hold[3], cash[3] - prices[4]) = max(-1, 5-4) = max(-1, 1) = 1
• cash[4] = max(cash[3], hold[3] + prices[4] - fee) = max(5, -1+4-2) = max(5, 1) = 5

第5天：

• hold[5] = max(hold[4], cash[4] - prices[5]) = max(1, 5-9) = max(1, -4) = 1
• cash[5] = max(cash[4], hold[4] + prices[5] - fee) = max(5, 1+9-2) = max(5, 8) = 8

步骤6：结果分析
最终结果是最后一天不持有股票的最大利润：cash[5] = 8

步骤7：空间优化
由于我们只需要前一天的hold和cash值，可以优化空间复杂度到O(1)：

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

关键理解点：

1. 手续费只在卖出时支付
2. hold状态表示当前持有股票，可能是之前买入或今天买入
3. cash状态表示当前不持有股票，可能是之前卖出或今天卖出
4. 最终答案是不持有股票的状态，因为持有股票还未实现利润