动态规划解决股票交易问题：LeetCode 188题详解

1. 问题背景与核心挑战LeetCode 188题买卖股票的最佳时机IV是动态规划系列中的经典难题它要求我们在最多完成k笔交易的前提下获取最大利润。这道题之所以被标记为Hard难度是因为它需要处理三个维度的状态变化天数、交易次数和持股状态。我在第一次遇到这个问题时被它的三维DP解法震撼到了。与简单的二维DP不同这里需要同时跟踪交易次数这个额外维度。实际面试中这道题经常出现在高频率交易公司的技术考核中比如对冲基金和量化交易相关的岗位。2. 动态规划状态定义解析2.1 三维状态矩阵构建我们需要定义一个三维DP数组dp[i][k][j]其中i 表示第i天0 ≤ i nk 表示剩余交易次数0 ≤ k ≤ Kj 表示持股状态0不持有1持有这个状态定义是解决问题的核心钥匙。我刚开始学习时常常混淆k的定义后来发现把它理解为剩余可交易次数更符合直觉——每次买入操作会消耗一次交易机会。2.2 状态转移方程推导基于上述定义我们可以建立状态转移方程第i天不持有股票 dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i])第i天持有股票 dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k1][0] - prices[i])这里有个关键点需要注意买入操作会消耗交易次数所以从k1转移过来。这个细节我当初调试了很久才发现。3. 边界条件与初始化技巧3.1 初始状态设置正确的初始化是DP问题成功的一半。对于这道题dp[0][k][0] 0 第一天不持有利润为0dp[0][k][1] -prices[0] 第一天买入利润为负股价dp[i][0][0] 0 没有交易机会利润为0dp[i][0][1] -infinity 没有交易机会却持有股票不可能特别注意当kn/2时问题退化为无限次交易情况可以用贪心算法优化。这是常见的性能优化点。3.2 遍历顺序选择三维DP的遍历顺序很重要。我推荐按以下顺序外层循环天数i从1到n-1中层循环交易次数k从K到1倒序内层处理持股状态j这种顺序可以确保在计算dp[i][k][j]时所需的子问题都已经被计算过。4. 空间优化实战技巧4.1 滚动数组优化原始三维DP的空间复杂度是O(nK2)我们可以优化到O(K*2)dp [[[0]*2 for _ in range(K1)] for __ in range(2)] for i in range(1, n): for k in range(K, 0, -1): dp[i%2][k][0] max(dp[(i-1)%2][k][0], dp[(i-1)%2][k][1] prices[i]) dp[i%2][k][1] max(dp[(i-1)%2][k][1], dp[(i-1)%2][k-1][0] - prices[i])4.2 交易次数剪枝当K ≥ n/2时相当于可以无限次交易此时问题简化为profit 0 for i in range(1, len(prices)): if prices[i] prices[i-1]: profit prices[i] - prices[i-1] return profit这个优化可以将最坏情况时间复杂度从O(nK)降到O(n)。5. 常见错误与调试技巧5.1 交易次数计算错误最常见的错误是混淆交易次数的增减逻辑。记住完整的买卖算一次交易在状态转移方程中只有买入操作会减少k5.2 边界条件遗漏容易忽略的边界情况价格列表为空K0K极大超过n/2的情况5.3 状态初始化错误持股状态的初始值容易设错。建议初始不持有利润0初始持有利润-prices[0]6. 完整代码实现与注释def maxProfit(k, prices): n len(prices) if n 0 or k 0: return 0 # 当k很大时退化为贪心算法 if k n // 2: profit 0 for i in range(1, n): if prices[i] prices[i-1]: profit prices[i] - prices[i-1] return profit # 初始化三维DP数组 dp [[[0]*2 for _ in range(k1)] for __ in range(n)] # 初始状态设置 for kk in range(k, 0, -1): dp[0][kk][0] 0 dp[0][kk][1] -prices[0] # 状态转移 for i in range(1, n): for kk in range(k, 0, -1): dp[i][kk][0] max(dp[i-1][kk][0], dp[i-1][kk][1] prices[i]) dp[i][kk][1] max(dp[i-1][kk][1], dp[i-1][kk-1][0] - prices[i]) return dp[n-1][k][0]7. 复杂度分析与优化对比7.1 时间复杂度原始三维DP时间复杂度O(n*K)空间复杂度O(nK2)优化后的滚动数组空间复杂度降为O(K*2)贪心优化后时间复杂度O(n)空间复杂度O(1)7.2 实际运行对比在我的测试中n1000, K100原始DP约120ms滚动数组优化约80ms贪心优化当K≥n/2约0.5ms8. 扩展思考与变种问题8.1 交易费用变种如果每笔交易有手续费fee只需修改状态转移方程dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i] - fee) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])8.2 冷冻期变种加入一天冷冻期卖出后不能立即买入dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) dp[i][k][1] max(dp[i-1][k][1], dp[i-2][k-1][0] - prices[i]) # 注意i-28.3 其他股票问题对比买卖一次LeetCode 121k1的特殊情况买卖无限次LeetCode 122k∞的情况含冷冻期LeetCode 309上述变种含手续费LeetCode 714上述变种9. 面试实战建议在面试中遇到这类问题时建议先明确状态定义和转移方程讨论边界条件和初始化提出空间优化方案讨论可能的变种情况写出清晰注释的代码我曾在面试中被要求在白板上推导这个三维DP的状态转移方程当时因为没有提前理清k的定义而卡壳。后来发现用具体的例子如k2手动模拟几次状态转移会很有帮助。