1. 问题背景与核心理解股票买卖时机选择是量化交易和算法设计中经典的时间序列分析问题。122题买卖股票的最佳时机II在LeetCode中属于动态规划系列但相比基础版本增加了关键限制条件允许无限次买卖但必须卖出手头股票后才能再次买入。这意味着我们需要在价格波动中捕捉所有可能的上升波段。这个问题的现实映射非常直接——它模拟了日内交易者的操作场景。假设你是一名短线操盘手每天收盘前必须平仓不能持仓过夜如何通过多次买卖获取最大累计收益比如给定价格序列[7,1,5,3,6,4]最优策略是在第2天买入第3天卖出收益4第4天买入第5天卖出收益3总收益7。关键洞察当允许无限次交易时最大收益等于所有上升波段差值的累加。这与现实交易中吃尽每个波段的思路完全一致。2. 暴力解法与问题规模分析最直观的方法是递归回溯所有可能的买卖组合。对于第i天我们有两种选择如果持有股票可以选择卖出或继续持有如果未持有可以选择买入或保持空仓这种解法的时间复杂度高达O(2^n)对于n1000的价格序列需要计算2^1000≈10^301种可能显然不可行。但理解这个暴力解法很重要因为它是优化解法的基础思维模型。def maxProfit(prices): def backtrack(index, holding): if index len(prices): return 0 if holding: # 可以选择卖出或持有 return max( prices[index] backtrack(index1, False), # 卖出 backtrack(index1, True) # 持有 ) else: # 可以选择买入或观望 return max( -prices[index] backtrack(index1, True), # 买入 backtrack(index1, False) # 观望 ) return backtrack(0, False)3. 动态规划的标准解法通过观察可以发现暴力解法中存在大量重复子问题。例如在第i天持有股票的状态下后续的最优解是确定的与如何到达第i天无关。这符合动态规划的最优子结构特性。我们定义两个状态数组hold[i]第i天结束时持有股票的最大收益cash[i]第i天结束时不持有股票的最大收益状态转移方程hold[i] max(hold[i-1], cash[i-1] - prices[i]) # 保持持有或当天买入 cash[i] max(cash[i-1], hold[i-1] prices[i]) # 保持空仓或当天卖出实现代码def maxProfit(prices): if not prices: return 0 hold [0] * len(prices) cash [0] * len(prices) hold[0] -prices[0] for i in range(1, len(prices)): hold[i] max(hold[i-1], cash[i-1] - prices[i]) cash[i] max(cash[i-1], hold[i-1] prices[i]) return cash[-1]这个解法时间复杂度O(n)空间复杂度O(n)。但观察状态转移可以发现当前状态只依赖前一个状态因此可以优化空间到O(1)def maxProfit(prices): hold, cash -float(inf), 0 for price in prices: hold max(hold, cash - price) cash max(cash, hold price) return cash4. 贪心算法的降维打击进一步分析问题特性会发现只要今天价格比昨天高就执行买卖操作。这种策略能捕获所有上升波段实现收益最大化。数学证明 设p[i] - p[i-1] delta 如果delta 0计入收益相当于在i-1天买入i天卖出 所有正delta之和就是最大可能收益实现代码极其简洁def maxProfit(prices): return sum(max(prices[i] - prices[i-1], 0) for i in range(1, len(prices)))这个解法时间复杂度O(n)空间复杂度O(1)是理论上的最优解。但要注意贪心策略的适用性依赖于本题的特殊条件——允许无限次交易且没有手续费。如果添加交易成本约束就必须回归动态规划解法。5. 不同解法的性能对比解法类型时间复杂度空间复杂度适用场景暴力递归O(2^n)O(n)仅用于教学理解动态规划O(n)O(n)通用解法空间优化DPO(n)O(1)推荐标准解法贪心算法O(n)O(1)无交易成本时最优6. 边界条件与异常处理实际编码中需要处理以下特殊情况空输入或单元素数组直接返回0单调递减序列收益为0包含重复元素不影响算法正确性极大值/极小值注意整型溢出Python无需考虑防御性编程示例def maxProfit(prices): if len(prices) 2: return 0 # 检查是否单调递减 is_descending True for i in range(1, len(prices)): if prices[i] prices[i-1]: is_descending False break if is_descending: return 0 # 正常处理 return sum(max(prices[i] - prices[i-1], 0) for i in range(1, len(prices)))7. 实际交易中的变体问题现实中的股票交易需要考虑更多因素这些变体问题可以作为练习含交易手续费每次卖出扣除固定费用解法修改DP状态转移方程卖出时扣除feecash[i] max(cash[i-1], hold[i-1] prices[i] - fee)含冷却期卖出后需等待1天才能买入解法增加第三个状态表示冷却期cooldown[i] cash[i-1] # 上一步卖出进入冷却 cash[i] max(cash[i-1], cooldown[i-1]) hold[i] max(hold[i-1], cash[i-1] - prices[i])最多完成k笔交易解法三维DP增加交易次数维度dp[k][i][0] max(dp[k][i-1][0], dp[k-1][i-1][1] prices[i]) dp[k][i][1] max(dp[k][i-1][1], dp[k][i-1][0] - prices[i])8. 算法选择与工程实践建议面试场景先提出暴力解法分析重复子问题引出DP优化空间复杂度最后讨论贪心解法的特殊性实际交易系统优先选择O(n)解法考虑使用numba加速循环对超长序列可采用分块并行计算添加异常检测模块监控算法输出测试用例设计test_cases [ ([], 0), # 空输入 ([1], 0), # 单元素 ([3,2,1], 0), # 单调减 ([1,2,3,4,5], 4), # 单调增 ([7,1,5,3,6,4], 7), # 随机波动 ([1,9,6,9,6,9], 16) # 多峰值 ]9. 数学视角的深入分析从信号处理角度看这个问题可以建模为价格序列P [p1, p2, ..., pn]差分序列D [p2-p1, p3-p2, ..., pn-p(n-1)]最大收益等于D中所有正数之和这引出一个有趣的性质最大收益与价格曲线的波动频率无关只与上升幅度总和有关。例如[1,3,5,7,9] 和 [1,9] 的最大收益相同8但前者的交易次数更多4次 vs 1次在实盘交易中这提示我们高频小幅波动可能不如低频大幅波动有利需要考虑交易成本对策略的影响波动率(volatility)与最终收益没有直接关系10. 从算法到交易策略的思考虽然这个算法在理论上完美但实际交易中直接应用会遇到以下问题未来函数问题算法假设知道未来价格实际只能基于历史数据滑点影响实际成交价与预期价格存在偏差流动性风险大额交易可能影响市场价格心理因素连续亏损后能否坚持执行策略改进思路加入移动平均线过滤假突破设置止损止盈阈值采用分批建仓策略结合波动率调整仓位大小一个简单的实盘策略框架class TradingStrategy: def __init__(self, window5): self.window window self.positions 0 def execute(self, price_history): if len(price_history) self.window 1: return 0 short_ma sum(price_history[-self.window:]) / self.window long_ma sum(price_history[-2*self.window:]) / self.window if short_ma long_ma and self.positions 0: # 金叉信号买入 self.positions 1 return 1 # 买入信号 elif short_ma long_ma and self.positions 0: # 死叉信号卖出 self.positions - 1 return -1 # 卖出信号 return 0这个策略虽然简单但已经包含了趋势跟踪的基本要素。算法题的解法则为我们提供了理论上的收益上限可以用来评估实际策略的有效性。 
长河君 · 2026/11/4 3:25:42 · 阅读 1.2k 动态规划与贪心算法解决股票买卖最佳时机问题
1. 问题背景与核心理解股票买卖时机选择是量化交易和算法设计中经典的时间序列分析问题。122题买卖股票的最佳时机II在LeetCode中属于动态规划系列但相比基础版本增加了关键限制条件允许无限次买卖但必须卖出手头股票后才能再次买入。这意味着我们需要在价格波动中捕捉所有可能的上升波段。这个问题的现实映射非常直接——它模拟了日内交易者的操作场景。假设你是一名短线操盘手每天收盘前必须平仓不能持仓过夜如何通过多次买卖获取最大累计收益比如给定价格序列[7,1,5,3,6,4]最优策略是在第2天买入第3天卖出收益4第4天买入第5天卖出收益3总收益7。关键洞察当允许无限次交易时最大收益等于所有上升波段差值的累加。这与现实交易中吃尽每个波段的思路完全一致。2. 暴力解法与问题规模分析最直观的方法是递归回溯所有可能的买卖组合。对于第i天我们有两种选择如果持有股票可以选择卖出或继续持有如果未持有可以选择买入或保持空仓这种解法的时间复杂度高达O(2^n)对于n1000的价格序列需要计算2^1000≈10^301种可能显然不可行。但理解这个暴力解法很重要因为它是优化解法的基础思维模型。def maxProfit(prices): def backtrack(index, holding): if index len(prices): return 0 if holding: # 可以选择卖出或持有 return max( prices[index] backtrack(index1, False), # 卖出 backtrack(index1, True) # 持有 ) else: # 可以选择买入或观望 return max( -prices[index] backtrack(index1, True), # 买入 backtrack(index1, False) # 观望 ) return backtrack(0, False)3. 动态规划的标准解法通过观察可以发现暴力解法中存在大量重复子问题。例如在第i天持有股票的状态下后续的最优解是确定的与如何到达第i天无关。这符合动态规划的最优子结构特性。我们定义两个状态数组hold[i]第i天结束时持有股票的最大收益cash[i]第i天结束时不持有股票的最大收益状态转移方程hold[i] max(hold[i-1], cash[i-1] - prices[i]) # 保持持有或当天买入 cash[i] max(cash[i-1], hold[i-1] prices[i]) # 保持空仓或当天卖出实现代码def maxProfit(prices): if not prices: return 0 hold [0] * len(prices) cash [0] * len(prices) hold[0] -prices[0] for i in range(1, len(prices)): hold[i] max(hold[i-1], cash[i-1] - prices[i]) cash[i] max(cash[i-1], hold[i-1] prices[i]) return cash[-1]这个解法时间复杂度O(n)空间复杂度O(n)。但观察状态转移可以发现当前状态只依赖前一个状态因此可以优化空间到O(1)def maxProfit(prices): hold, cash -float(inf), 0 for price in prices: hold max(hold, cash - price) cash max(cash, hold price) return cash4. 贪心算法的降维打击进一步分析问题特性会发现只要今天价格比昨天高就执行买卖操作。这种策略能捕获所有上升波段实现收益最大化。数学证明 设p[i] - p[i-1] delta 如果delta 0计入收益相当于在i-1天买入i天卖出 所有正delta之和就是最大可能收益实现代码极其简洁def maxProfit(prices): return sum(max(prices[i] - prices[i-1], 0) for i in range(1, len(prices)))这个解法时间复杂度O(n)空间复杂度O(1)是理论上的最优解。但要注意贪心策略的适用性依赖于本题的特殊条件——允许无限次交易且没有手续费。如果添加交易成本约束就必须回归动态规划解法。5. 不同解法的性能对比解法类型时间复杂度空间复杂度适用场景暴力递归O(2^n)O(n)仅用于教学理解动态规划O(n)O(n)通用解法空间优化DPO(n)O(1)推荐标准解法贪心算法O(n)O(1)无交易成本时最优6. 边界条件与异常处理实际编码中需要处理以下特殊情况空输入或单元素数组直接返回0单调递减序列收益为0包含重复元素不影响算法正确性极大值/极小值注意整型溢出Python无需考虑防御性编程示例def maxProfit(prices): if len(prices) 2: return 0 # 检查是否单调递减 is_descending True for i in range(1, len(prices)): if prices[i] prices[i-1]: is_descending False break if is_descending: return 0 # 正常处理 return sum(max(prices[i] - prices[i-1], 0) for i in range(1, len(prices)))7. 实际交易中的变体问题现实中的股票交易需要考虑更多因素这些变体问题可以作为练习含交易手续费每次卖出扣除固定费用解法修改DP状态转移方程卖出时扣除feecash[i] max(cash[i-1], hold[i-1] prices[i] - fee)含冷却期卖出后需等待1天才能买入解法增加第三个状态表示冷却期cooldown[i] cash[i-1] # 上一步卖出进入冷却 cash[i] max(cash[i-1], cooldown[i-1]) hold[i] max(hold[i-1], cash[i-1] - prices[i])最多完成k笔交易解法三维DP增加交易次数维度dp[k][i][0] max(dp[k][i-1][0], dp[k-1][i-1][1] prices[i]) dp[k][i][1] max(dp[k][i-1][1], dp[k][i-1][0] - prices[i])8. 算法选择与工程实践建议面试场景先提出暴力解法分析重复子问题引出DP优化空间复杂度最后讨论贪心解法的特殊性实际交易系统优先选择O(n)解法考虑使用numba加速循环对超长序列可采用分块并行计算添加异常检测模块监控算法输出测试用例设计test_cases [ ([], 0), # 空输入 ([1], 0), # 单元素 ([3,2,1], 0), # 单调减 ([1,2,3,4,5], 4), # 单调增 ([7,1,5,3,6,4], 7), # 随机波动 ([1,9,6,9,6,9], 16) # 多峰值 ]9. 数学视角的深入分析从信号处理角度看这个问题可以建模为价格序列P [p1, p2, ..., pn]差分序列D [p2-p1, p3-p2, ..., pn-p(n-1)]最大收益等于D中所有正数之和这引出一个有趣的性质最大收益与价格曲线的波动频率无关只与上升幅度总和有关。例如[1,3,5,7,9] 和 [1,9] 的最大收益相同8但前者的交易次数更多4次 vs 1次在实盘交易中这提示我们高频小幅波动可能不如低频大幅波动有利需要考虑交易成本对策略的影响波动率(volatility)与最终收益没有直接关系10. 从算法到交易策略的思考虽然这个算法在理论上完美但实际交易中直接应用会遇到以下问题未来函数问题算法假设知道未来价格实际只能基于历史数据滑点影响实际成交价与预期价格存在偏差流动性风险大额交易可能影响市场价格心理因素连续亏损后能否坚持执行策略改进思路加入移动平均线过滤假突破设置止损止盈阈值采用分批建仓策略结合波动率调整仓位大小一个简单的实盘策略框架class TradingStrategy: def __init__(self, window5): self.window window self.positions 0 def execute(self, price_history): if len(price_history) self.window 1: return 0 short_ma sum(price_history[-self.window:]) / self.window long_ma sum(price_history[-2*self.window:]) / self.window if short_ma long_ma and self.positions 0: # 金叉信号买入 self.positions 1 return 1 # 买入信号 elif short_ma long_ma and self.positions 0: # 死叉信号卖出 self.positions - 1 return -1 # 卖出信号 return 0这个策略虽然简单但已经包含了趋势跟踪的基本要素。算法题的解法则为我们提供了理论上的收益上限可以用来评估实际策略的有效性。