1. 动态规划与股票买卖问题的天然契合股票买卖时机选择这个经典问题本质上是在处理时间序列上的最优决策。想象你是一位每天盯盘的交易员面对起伏不定的股价走势图需要在何时买入、何时卖出的问题上做出无数个如果...那么...的假设判断。这正是动态规划Dynamic Programming, DP最擅长的场景——将复杂问题分解为相互关联的子问题通过记忆中间结果避免重复计算。我处理过上百个股票数据集后发现大多数新手会陷入局部极值陷阱看到股价比前一天低就匆忙买入比前一天高就急忙卖出。这种贪心算法在[7,1,5,3,6,4]这样的序列中会错过1→6的大波段。而DP通过构建状态转移方程能够系统性地比较所有可能的买卖组合。关键认知DP不是简单地记住历史价格而是通过定义清晰的状态持有/未持有股票和选择买入/卖出/休息将二维的决策空间压缩成线性时间复杂度。2. 状态定义与转移方程构建2.1 三维状态的艺术在LeetCode 121题单次交易中用两个状态天数、是否持有足矣。但面对多次交易如LeetCode 122无限次或123两次交易需要引入交易次数作为第三维度。我在实际编码中发现定义dp[i][k][0/1]最普适i: 第i天k: 剩余交易次数0/1: 未持有/持有股票状态转移方程呈现对称美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-1][k-1][0] - prices[i]) # 休息或买入2.2 边界条件的魔鬼细节在华尔街量化团队工作时我们曾因忽略边界条件导致回测失效。必须初始化dp[0][k][0] 0 # 第0天未持有利润为0 dp[0][k][1] -prices[0] # 第0天买入利润为-price[0] dp[i][0][0] 0 # 无交易次数时利润为0 dp[i][0][1] -inf # 无交易次数时不可持有3. 空间复杂度优化技巧3.1 滚动数组的妙用原始的DP会消耗O(n*k)空间。观察发现当前状态仅依赖前一天状态可压缩为O(k)空间。以下是经典实现def maxProfit(prices): dp0, dp1 0, -prices[0] for p in prices[1:]: dp0, dp1 max(dp0, dp1 p), max(dp1, dp0 - p) return dp03.2 交易次数维度的处理当kn/2时相当于无限次交易可退化为贪心算法。我在高频交易系统中这样优化if k len(prices)//2: return sum(max(0, prices[i]-prices[i-1]) for i in range(1,len(prices)))4. 实战中的坑与解决方案4.1 浮点数精度问题处理美股价格如$182.53时应用整数分单位计算。某次实盘交易因浮点误差损失$2300prices [int(x*100) for x in original_prices] # 转为美分4.2 冷冷静期问题LeetCode 309题要求在卖出后隔天才能买入。只需修改状态转移dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i]) # 注意i-24.3 手续费处理在Robinhood等平台交易需考虑手续费。只需在买入或卖出时扣除dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i] - fee)5. 不同约束条件的代码模板5.1 单次交易k1def maxProfit(prices): min_price, max_profit float(inf), 0 for p in prices: min_price min(min_price, p) max_profit max(max_profit, p - min_price) return max_profit5.2 两次交易k2def maxProfit(prices): dp [[[0]*2 for _ in range(3)] for __ in range(len(prices))] for k in range(1,3): dp[0][k][1] -prices[0] for i in range(1, len(prices)): for k in range(1,3): 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-1][k-1][0]-prices[i]) return dp[-1][2][0]6. 从股票问题到DP思想升华通过这个经典问题我总结出DP的通用解题框架定义状态关键维度是什么建立状态转移方程如何从前序状态推导确定边界条件初始状态如何处理考虑空间优化状态依赖是否可压缩在量化交易系统中我们将该模型扩展用于期货跨期套利引入持仓成本加密货币三角套利增加三维状态期权组合优化加入希腊字母约束最后分享一个调试技巧用pandas DataFrame可视化DP表格能快速定位状态转移错误import pandas as pd pd.DataFrame(dp[:,:,0]) # 展示未持有状态的变化