线性动态规划：买卖股票的最佳时机 IV（进阶版——带交易次数的限制与交易费用）

题目描述
给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格。
你最多可以完成 k 笔交易（买入和卖出合为一笔交易，且必须在再次买入前卖出已有的股票）。
同时，每笔交易需要支付固定的手续费 fee（在卖出股票时支付）。
请计算你能够获得的最大利润。
注意：你不能同时持有多笔交易（即必须在再次买入前卖出当前持有的股票）。

示例
输入：prices = [1, 3, 2, 8, 4, 9], k = 2, fee = 2
输出：8
解释：

• 第一天买入（价格1），第四天卖出（价格8），利润 = 8-1-2 = 5
• 第五天买入（价格4），第六天卖出（价格9），利润 = 9-4-2 = 3
  总利润 = 5+3 = 8

解题过程

1. 问题理解

• 这是经典的“买卖股票”问题的进阶版，加入了 交易次数限制 k 和 交易费用 fee。
• 状态需要考虑：当前是第几天、当前交易次数、当前是否持有股票。
• 目标是最大化最终利润，且不能持股结束（但允许最后一天卖出）。

2. 定义状态
定义 dp[i][j][0] 和 dp[i][j][1]：

• i 表示第 i 天（0 ≤ i ≤ n-1），这里用天数索引。
• j 表示已经完成的交易次数（0 ≤ j ≤ k）。
• dp[i][j][0] 表示第 i 天结束时，没有持有股票，且已经完成了 j 笔交易的最大利润。
• dp[i][j][1] 表示第 i 天结束时，持有股票，且已经完成了 j 笔交易的最大利润。

注意：一次“交易”指一次买入和一次卖出。我们可以在买入时增加交易计数，也可以在卖出时增加，但必须统一。
常用定义：在 卖出股票时 增加交易计数。这样，j 表示已经卖出 j 次（即已完成 j 笔交易）。

3. 状态转移方程
对于第 i 天（i ≥ 1）：

• 如果没有持股 dp[i][j][0]，可能是前一天就没持股，或者前一天持股今天卖出：
  dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] + prices[i] - fee)
  注意：j-1 必须 ≥ 0，卖出后才算完成一笔交易，所以从持股状态 j-1 卖出到 j。

• 如果持股 dp[i][j][1]，可能是前一天就持股，或者前一天没持股今天买入：
  dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])
  注意：买入不增加交易次数，所以交易次数 j 不变。

边界情况：

• 当 j = 0 时，dp[i][0][0] 表示没有交易，不持股，利润为 0。
• 当 j = 0 时，dp[i][0][1] 表示没有交易却持股，这是不可能的（除非允许初始买入？但 j=0 持股意味着买入了但未卖出，此时交易次数是 0，但持股中，这种情况是允许的，只是还未完成交易）。实际上，dp[i][0][1] 可以从前一天的 dp[i-1][0][1] 或初始买入得到。
  我们初始化 dp[0][0][1] = -prices[0]，表示第 0 天买入，其他 dp[0][j][1] 不可能（j>0 时持股？不可能，因为还没卖出过，所以设为 -∞）。

4. 初始化

• dp[0][0][0] = 0 （第 0 天，不持股，交易次数 0）
• dp[0][0][1] = -prices[0] （第 0 天买入，持股，交易次数 0）
• 对于 j > 0 的情况：
  dp[0][j][0] = -∞ （第 0 天不可能已经完成交易）
  dp[0][j][1] = -∞ （第 0 天持股且已完成 j>0 笔交易，不可能）

5. 最终答案
最后一天（i = n-1）时，可能完成任意笔交易（0 到 k 笔），且最终必须不持股（因为持股没卖出会亏）。
所以答案是：max(dp[n-1][j][0])，其中 j 从 0 到 k。

6. 空间优化
注意到 dp[i] 只依赖于 dp[i-1]，可以只用二维数组 dp[j][state] 来优化空间。

7. 实现细节

• 用负无穷大表示不可能状态。
• 注意 j 的遍历顺序，避免状态覆盖问题。在递推时，如果是从前一天的状态来，j 从小到大或从大到小都可以，但要保证用到的 dp[i-1][j-1] 是上一层的值。
• 如果采用滚动数组，j 应该从大到小遍历，因为 dp[j][0] 用到了 dp[j-1][1]，如果 j 从小到大，会用到本层更新后的值，这是错误的。

8. 示例推演
prices = [1, 3, 2, 8, 4, 9], k=2, fee=2

初始化：
dp[0][0][0]=0, dp[0][0][1]=-1
dp[0][1][0]=-∞, dp[0][1][1]=-∞
dp[0][2][0]=-∞, dp[0][2][1]=-∞

逐天计算（略过中间步骤，展示最终结果）得到：
最后一天，dp[5][0][0]=0, dp[5][1][0]=3, dp[5][2][0]=8
最大值为 8。

9. 代码框架（Python）

def maxProfit(prices, k, fee):
    n = len(prices)
    if n < 2 or k == 0:
        return 0
    
    # 初始化 dp[j][0] 和 dp[j][1]
    dp = [[0, float('-inf')] for _ in range(k+1)]
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    
    for i in range(1, n):
        # 注意 j 从大到小，避免覆盖
        for j in range(k, 0, -1):
            # 卖出，完成一笔交易
            dp[j][0] = max(dp[j][0], dp[j-1][1] + prices[i] - fee)
            # 买入，不增加交易次数
            dp[j][1] = max(dp[j][1], dp[j][0] - prices[i])
        # j=0 的情况单独处理，因为没有 j-1
        dp[0][1] = max(dp[0][1], dp[0][0] - prices[i])
    
    # 最终答案是所有 j 中不持股的最大值
    ans = 0
    for j in range(k+1):
        ans = max(ans, dp[j][0])
    return ans

10. 边界情况

• 如果 k 很大（≥ n/2），相当于无限次交易，可以简化成贪心算法，每次有利润就交易。
• 如果 fee 很大，可能交易不划算。
• 如果 prices 单调递减，最大利润为 0（不交易）。

总结
本题的关键在于定义状态时明确“交易次数”的含义（在卖出时增加），并正确处理不可能状态的初始化。通过三维 DP 的思路，再优化到二维滚动数组，可以高效求解。