动态规划解决含手续费股票交易问题-北京尧图网络

1. 问题背景与核心挑战股票交易中的动态规划问题一直是算法领域的经典题型。714 买卖股票的最佳时机含手续费这道题目在传统股票买卖问题基础上增加了手续费这一现实因素使得状态转移逻辑更加复杂。这类问题考察的是对交易规则的数学建模能力和动态规划思想的灵活运用。在实际交易场景中手续费是不可避免的成本因素。以A股市场为例买卖双向通常收取0.025%-0.3%不等的手续费不同券商有差异。当进行高频交易或小额交易时手续费对最终收益的影响会变得非常显著。这就需要在算法设计中精确计算手续费对买卖决策的影响。2. 问题建模与关键分析2.1 问题形式化描述给定一个整数数组prices表示股票每日价格其中prices[i]是第i天的股票价格整数fee表示交易股票的手续费用。你可以无限次地完成交易但每次交易都需要付手续费。要求计算可获得的最大利润。示例输入prices [1, 3, 2, 8, 4, 9], fee 2 输出8 解释在1买入8卖出利润8-1-25在4买入9卖出利润9-4-23。总利润538。2.2 与经典问题的区别相比经典的122 买卖股票的最佳时机II问题无限次交易无手续费本题增加了两个关键约束每次卖出时需要支付固定金额fee不是按比例手续费只在卖出时收取根据题意假设这使得贪心算法不再适用必须采用动态规划来跟踪持有/未持有两种状态下的最大收益。3. 动态规划解法详解3.1 状态定义定义两个状态数组hold[i]第i天结束时持有股票时的最大利润cash[i]第i天结束时不持有股票时的最大利润初始状态hold[0] -prices[0] 第一天买入cash[0] 0 第一天不操作3.2 状态转移方程对于第i天i 0hold[i] max(hold[i-1], cash[i-1] - prices[i])保持前一天的持有状态或者前一天未持有今天买入cash[i] max(cash[i-1], hold[i-1] prices[i] - fee)保持前一天未持有状态或者前一天持有今天卖出需扣除手续费3.3 空间优化由于每天的状态只依赖前一天的状态可以将空间复杂度从O(n)优化到O(1)def maxProfit(prices, fee): hold, cash -prices[0], 0 for i in range(1, len(prices)): hold max(hold, cash - prices[i]) cash max(cash, hold prices[i] - fee) return cash4. 关键点解析与验证4.1 为什么不能使用贪心算法在无手续费的无限交易问题中可以采用所有上升段都交易的贪心策略。但加入手续费后频繁交易可能导致利润被手续费蚕食。例如 prices [1,3,7,5,10,3], fee3 贪心策略(1买3卖)(3买7卖)(5买10卖) (3-1-3)(7-3-3)(10-5-3) -1122 最优策略1买10卖 10-1-364.2 手续费收取时机的处理根据题目描述手续费在卖出时收取。如果题目改为买入时收取状态转移方程需要相应调整 cash[i] max(cash[i-1], hold[i-1] prices[i]) hold[i] max(hold[i-1], cash[i-1] - prices[i] - fee)4.3 边界条件测试用例单边下跌行情 prices [7,6,5,4,3], fee2 预期输出0不交易手续费为0 prices [1,2,3,4,5], fee0 预期输出44次交易或1次交易结果相同波动剧烈 prices [1,10,1,10,1], fee2 预期输出141买10卖 1买10卖5. 复杂度分析与优化5.1 时间复杂度两种实现方式基础DPO(n)时间O(n)空间优化DPO(n)时间O(1)空间由于必须遍历整个价格序列O(n)已经是理论下限。5.2 实际运行效率在LeetCode测试中优化后的DP解法运行时间800-900msPython3内存消耗21MB左右进一步优化空间有限主要瓶颈在于Python的解释执行速度。6. 不同语言实现对比6.1 Java实现class Solution { public int maxProfit(int[] prices, int fee) { int hold -prices[0], cash 0; for (int i 1; i prices.length; i) { cash Math.max(cash, hold prices[i] - fee); hold Math.max(hold, cash - prices[i]); } return cash; } }特点类型明确运行速度更快约3-5ms6.2 C实现class Solution { public: int maxProfit(vectorint prices, int fee) { int hold -prices[0], cash 0; for (int i 1; i prices.size(); i) { cash max(cash, hold prices[i] - fee); hold max(hold, cash - prices[i]); } return cash; } };特点运行速度最快约20-40μs7. 实际交易中的应用启示虽然这是一个算法题但其核心思想对真实交易有参考价值高频交易的陷阱即使每次交易都能获利频繁交易可能导致手续费吞噬利润持仓成本计算需要精确计算包含手续费后的实际买入成本止盈策略调整预期收益必须超过手续费才有交易价值在真实量化交易系统中手续费是必须纳入交易策略的重要参数。通常需要设置最小预期收益阈值如手续费的两倍才会触发交易信号。8. 常见错误与调试技巧8.1 初始化错误常见错误hold初始化为0而非-prices[0] 表现会错过第一天买入的机会调试检查初始状态是否符合第一天买入的逻辑8.2 状态更新顺序错误写法hold max(hold, cash - prices[i]) cash max(cash, hold prices[i] - fee)问题使用了更新后的hold计算cash 正确顺序应该先用前一天的hold计算cash8.3 手续费处理位置错误在买入和卖出时都扣除fee 表现利润计算偏小调试确认题目要求的手续费收取时机9. 相关题目拓展基础版本买卖股票的最佳时机单次交易买卖股票的最佳时机II无限次交易无手续费进阶版本买卖股票的最佳时机III最多两次交易买卖股票的最佳时机IV最多k次交易最佳买卖股票时机含冷冻期变种问题含交易税按比例收费买卖手续费不同分阶段不同手续费率10. 学习建议与总结掌握这类问题的核心在于明确状态定义持有/未持有正确列出状态转移方程处理好边界条件和初始状态根据题目特点调整手续费处理逻辑建议从基础版本开始练习逐步增加约束条件体会状态设计的变化。可以尝试用纸笔模拟小规模案例的状态转移过程加深理解。

动态规划解决含手续费股票交易问题

相关推荐

Terra：Rust+WASM重构的3D GIS引擎与真实大气渲染

C语言结构体：自定义数据类型详解与实践

ERP实施效率陷阱解析与破局之道

更多资讯

GS相位恢复算法：傅里叶迭代与计算全息Python实战

论文降重避坑指南：如何识别不可靠的文本改写服务

别让论文“降重”变成“降智”：如何甄别与规避不可靠的文本改写服务

Vant RollingText 翻滚文本组件实战指南：数字与文本翻滚动效的配置、原理与手动控制

ESP32-P4 USB Host U盘实验：TinyUSB与FATFS全链路解析

帝国CMS 7.5后台响应式模板V2.4：安装部署与二次开发指南

今日更新

SpacetimeDB C++ 模块库实战：用 C++20 在数据库内构建 WebAssembly 模块

别踩雷！不是所有 AI 写作工具都靠谱，2026 高校认可工具精选

SSM+MySQL幼儿园管理系统源码解析：从部署到优化

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？