线性动态规划：带限制的股票买卖问题（最多完成k笔交易，且每次交易有手续费） 问题描述 给定一个整数数组 prices ，其中 prices[i] 表示某支股票在第 i 天的价格。你可以完成 最多 k 笔交易 ，但需要遵守以下规则： 在买入股票之前，你必须卖出之前持有的股票（即不能同时持有多笔交易）。 每笔交易（一次买入和一次卖出合为一笔交易）需要支付一次固定的手续费 fee （在卖出时支付）。 你不能在同一天进行多次交易（即每天最多只能进行一次操作：买入、卖出或什么都不做）。 请计算你能够获得的最大利润。如果无法获得任何利润，则返回 0。 示例 1 ： 输入： prices = [1, 3, 2, 8, 4, 9] , k = 2 , fee = 2 输出：8 解释： 第一笔交易：第1天买入（价格1），第4天卖出（价格8），利润 = 8-1-2 = 5。 第二笔交易：第5天买入（价格4），第6天卖出（价格9），利润 = 9-4-2 = 3。 总利润 = 5+3 = 8。 示例 2 ： 输入： prices = [1, 3, 7, 5, 10, 3] , k = 2 , fee = 3 输出：6 解释： 第一笔交易：第1天买入（价格1），第3天卖出（价格7），利润 = 7-1-3 = 3。 第二笔交易：第4天买入（价格5），第5天卖出（价格10），利润 = 10-5-3 = 2。 总利润 = 3+2 = 6。 问题本质 ：这是一个带有交易次数限制和交易手续费的股票买卖问题，属于线性动态规划中的状态机模型。 解题思路 我们可以将每天的状态分为两种： 持有股票 和 不持有股票 。但这里还限制了最多完成 k 笔交易，因此我们需要记录已经完成的交易次数（买入和卖出合为一笔）。然而，为了简化状态，我们可以在 买入股票时 增加交易次数（因为一笔交易从买入开始）。这样，动态规划的状态定义可以如下： 定义 dp[i][j][0] 表示在第 i 天结束时，最多完成了 j 笔交易（注意：这里的交易次数以买入计数），且 当前不持有股票 的最大利润。 定义 dp[i][j][1] 表示在第 i 天结束时，最多完成了 j 笔交易，且 当前持有股票 的最大利润。 状态转移方程 ： 对于 dp[i][j][0] （第i天不持有股票）： 可能由前一天也不持有股票转移而来： dp[i-1][j][0] 可能由前一天持有股票，但在第i天卖出转移而来： dp[i-1][j][1] + prices[i] - fee （卖出时支付手续费） 取两者最大值： dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i] - fee) 对于 dp[i][j][1] （第i天持有股票）： 可能由前一天也持有股票转移而来： dp[i-1][j][1] 可能由前一天不持有股票，但在第i天买入转移而来： dp[i-1][j-1][0] - prices[i] （注意：买入时交易次数增加1，所以是 j-1 转移到 j ） 取两者最大值： dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) 边界条件 ： 第0天（即未开始时）： 不持有任何股票： dp[0][j][0] = 0 （利润为0） 持有股票： dp[0][j][1] = -∞ （不可能发生，用负无穷表示） 交易次数为0时（即不允许交易）： 不持有股票： dp[i][0][0] = 0 持有股票： dp[i][0][1] = -∞ （不允许交易，不可能持有股票） 最终答案 ： 因为最多可以完成k笔交易，且最终不持有股票才能获得最大利润（持有股票未卖出会亏损），所以答案为 dp[n-1][k][0] ，其中 n 是 prices 的长度。 详细步骤 初始化 ： 设 n = len(prices) 。 创建一个三维数组 dp ，大小为 (n, k+1, 2) ，并初始化为一个很小的负数（如 -1e9 ），表示不可能状态。 对于所有交易次数 j （0到k），设置第0天的状态： dp[0][j][0] = 0 dp[0][j][1] = -prices[0] （注意：这里与标准定义略有不同，因为第一天买入，交易次数应为1，但我们用 j 表示“最多完成了j笔交易”，所以当 j>=1 时， dp[0][j][1] = -prices[0] ；当 j=0 时，应为负无穷。但为了简化，我们可以统一处理：在状态转移中，当 j=0 时， dp[i][0][1] 不会从 j-1 转移，所以只需初始化 dp[0][0][1] = -∞ ， dp[0][j][1] = -prices[0] 当 j>=1 。然而，更清晰的写法是单独处理第一天。） 更清晰的初始化方法 ： 先初始化 dp[0][0][0] = 0 （第0天，交易0次，不持有股票）。 对于 j 从1到k，设置 dp[0][j][0] = 0 （实际上，第一天不买入，不持有股票，利润为0）。 对于 j 从1到k，设置 dp[0][j][1] = -prices[0] （第一天买入，交易次数变为1，所以只有 j>=1 时才能持有股票）。 设置 dp[0][0][1] = -∞ （不允许交易时不可能持有股票）。 状态转移 ： 从第1天到第n-1天（ i 从1到n-1）： 先处理交易次数为0的情况： dp[i][0][0] = 0 ， dp[i][0][1] = -∞ 。 对于交易次数 j 从1到k： 不持有股票： dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i] - fee) 持有股票： dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) 答案 ： 遍历所有交易次数 j 从0到k，取 dp[n-1][j][0] 的最大值。但注意，题目是“最多完成k笔交易”，所以最终状态交易次数不超过k即可，但交易次数少可能利润更大，所以我们需要取 max(dp[n-1][j][0]) 对于 j=0..k 。然而，由于交易可能带来正利润，通常交易次数多用尽可能更好，但因为有手续费，可能交易次数少更优，所以需遍历。 优化思路 空间优化：由于 dp[i] 只依赖于 dp[i-1] ，可以将三维数组优化为二维数组，即只保留交易次数和状态两个维度，滚动更新。 交易次数限制优化：如果 k 非常大（例如 k >= n/2 ），那么相当于没有交易次数限制，可以退化为普通的带手续费的股票买卖问题（贪心或动态规划）。 复杂度分析 时间复杂度：O(n * k)，其中 n 是 prices 的长度。 空间复杂度：优化后为 O(k)。 示例演算（示例1） 输入： prices = [1, 3, 2, 8, 4, 9] , k = 2 , fee = 2 初始化（n=6）： 创建 dp[6][3][2] （交易次数0,1,2，所以k+1=3）。 第0天（价格1）： dp[0][0][0] = 0 dp[0][1][0] = 0 dp[0][2][0] = 0 dp[0][0][1] = -∞ dp[0][1][1] = -1 dp[0][2][1] = -1 状态转移（只展示关键步骤）： 第1天（价格3）： j=1: 不持有： max(dp[0][1][0], dp[0][1][1]+3-2) = max(0, -1+1) = 0 持有： max(dp[0][1][1], dp[0][0][0]-3) = max(-1, 0-3) = -1 j=2: 类似计算（略） ... 依次计算到最后一天。 最终， dp[5][2][0] 为8，即最大利润。 总结 这个问题是经典股票买卖问题的综合变体，结合了交易次数限制和手续费。通过定义状态为“天数、交易次数、是否持有股票”，可以系统地推导出状态转移方程。注意边界条件的处理，特别是交易次数为0时不能持有股票。最终答案需遍历所有可能的交易次数取最大值。在实际编码中，可以进行空间优化以提升效率。