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 dp0

3.2 交易次数维度的处理

当k>n/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）时，应用整数分单位计算。某次实盘交易因浮点误差损失$2300：

prices = [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-2

4.3 手续费处理

在Robinhood等平台交易需考虑手续费。只需在买入或卖出时扣除：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)

5. 不同约束条件的代码模板

5.1 单次交易（k=1）

def 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_profit

5.2 两次交易（k=2）

def 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的通用解题框架：

1. 定义状态（关键维度是什么？）
2. 建立状态转移方程（如何从前序状态推导？）
3. 确定边界条件（初始状态如何处理？）
4. 考虑空间优化（状态依赖是否可压缩？）

在量化交易系统中，我们将该模型扩展用于：

• 期货跨期套利（引入持仓成本）
• 加密货币三角套利（增加三维状态）
• 期权组合优化（加入希腊字母约束）

最后分享一个调试技巧：用pandas DataFrame可视化DP表格，能快速定位状态转移错误：

import pandas as pd pd.DataFrame(dp[:,:,0]) # 展示未持有状态的变化