动态规划解决股票买卖的最佳时机问题（进阶版） 题目描述 给定一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。设计算法计算在最多完成 k 笔交易（即买入和卖出合为一笔交易）的情况下，能获取的最大利润。注意：不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。 解题过程 1. 问题分析 这是股票买卖系列中的进阶问题，它引入了交易次数限制 k 。我们需要一个动态规划（DP）方法来处理状态转移。核心在于定义状态，并考虑交易次数。 2. 状态定义 定义三维 DP 数组： dp[i][k][0] ：第 i 天结束时，最多进行 k 次交易，且 当前不持有股票 的最大利润。 dp[i][k][1] ：第 i 天结束时，最多进行 k 次交易，且 当前持有股票 的最大利润。 状态解释 ： i 表示天数（0 ≤ i ≤ n-1）。 k 表示最多交易次数（注意：一次买入+卖出才算一次交易）。 第三维 0/1 表示是否持有股票。 3. 状态转移方程 我们需要考虑每天的操作：买入、卖出或休息。 基础情况 ： 当 k = 0 时，不允许交易，利润为 0。 当 i = 0 （第一天）时： dp[0][k][0] = 0 （第一天不持有股票，利润为 0）。 dp[0][k][1] = -prices[0] （第一天持有股票，表示买入，利润为负的股价）。 转移方程 ： 第 i 天不持有股票 ( dp[i][k][0] )： 可能昨天就不持有，今天休息： dp[i-1][k][0] 可能昨天持有，今天卖出（完成一次交易）： dp[i-1][k][1] + prices[i] 取最大值： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) 第 i 天持有股票 ( dp[i][k][1] )： 可能昨天就持有，今天休息： dp[i-1][k][1] 可能昨天不持有，今天买入（注意：买入会消耗一次交易机会）： dp[i-1][k-1][0] - prices[i] 取最大值： dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) 4. 初始化 当 k = 0 时：对于所有 i ， dp[i][0][0] = 0 ， dp[i][0][1] = -∞ （不可能持有股票）。 当 i = 0 时： dp[0][k][0] = 0 dp[0][k][1] = -prices[0] 5. 时间复杂度优化 如果 k 很大（比如 k > n/2 ），问题退化为无限次交易，可以用贪心法解决（因为交易次数足够覆盖所有上涨波段）。具体做法：遍历价格，只要今天价格比昨天高，就累加利润。 6. 算法步骤 如果 k <= 0 或数组长度 n <= 1 ，直接返回 0。 如果 k >= n/2 ，使用贪心法计算最大利润。 否则，使用三维 DP： 初始化 DP 数组，大小为 (n, k+1, 2) 。 填充 k=0 和 i=0 的基础情况。 遍历 i 从 1 到 n-1，遍历 j 从 1 到 k，更新状态。 最终答案是 dp[n-1][k][0] （最后一天不持有股票时的最大利润）。 7. 示例 假设 prices = [3,2,6,5,0,3] ， k = 2 。 DP 表计算 （简化表示，只展示关键步骤）： 初始化： dp[0][1][0]=0 , dp[0][1][1]=-3 , dp[0][2][0]=0 , dp[0][2][1]=-3 第 1 天（i=1, price=2）： dp[1][1][0] = max(0, -3+2) = 0 dp[1][1][1] = max(-3, 0-2) = -2 dp[1][2][0] = max(0, -3+2) = 0 dp[1][2][1] = max(-3, 0-2) = -2 继续计算到最后一天，最终 dp[5][2][0] = 7 （对应交易：第2天买入，第3天卖出，利润4；第5天买入，第6天卖出，利润3；总利润7）。 8. 关键点总结 状态定义要清晰，区分交易次数和持有状态。 注意边界条件，尤其是 k=0 和 i=0 的情况。 当 k 较大时，使用贪心优化避免不必要的 DP 计算。 实际代码中可以用滚动数组优化空间，将三维 DP 压缩为二维（因为 dp[i] 只依赖 dp[i-1] ）。 通过以上步骤，我们就能高效解决带交易次数限制的股票买卖问题。