用途
dp-optimizer 是一个面向动态规划代码的优化技能,目标是自动为已有 DP 解法应用高级优化手段,改善时间复杂度或空间复杂度。资料中列出的目标处理流程包括 dp-state-optimization、advanced-dp-techniques 和 complexity-optimization。
主要能力
该技能声称支持以下优化技术:
时间优化
- 凸包优化(Convex Hull Trick):对特定递推式,把 O(n^2) 降为 O(n log n)。
- 分治优化(Divide and Conquer):当最优决策点 j 具有单调性时,把 O(n^2 k) 降为 O(n k log n)。
- Knuth 优化:对特定区间 DP,把 O(n^3) 降为 O(n^2)。
- 单调队列/双端队列优化:对滑动窗口型 DP,把 O(n*k) 降为 O(n)。
空间优化
- 滚动数组:当转移只需上一行状态时,把 O(n*m) 降为 O(m)。
- 位掩码压缩:通过位运算减少状态空间。
此外还列出 Alien's trick / WQS 二分作为可选技术。
使用方式
技能定义了输入与输出结构。
输入(JSON 对象)字段:
- dpCode:待优化的 DP 代码(必填)。
- optimizationType:优化类型(必填),可选值为 auto、convexHull、divideConquer、knuth、monotonic、space。
- stateDefinition:状态定义(可选)。
- transitions:状态转移(可选)。
- currentComplexity:当前复杂度(可选)。
- targetComplexity:目标复杂度(可选)。
示例输入结构: { "dpCode": "...", "optimizationType": "auto" }
输出(JSON 对象)字段:
- success:是否成功(必填)。
- optimizedCode:优化后的代码。
- optimizationApplied:所应用的优化。
- newComplexity:新的复杂度。
- explanation:说明。
示例输出结构: { "success": true, "optimizedCode": "...", "optimizationApplied": "...", "newComplexity": "...", "explanation": "..." }
适用场景
适合需要改进已有动态规划实现性能的算法开发场景,例如竞赛编程中 DP 超时或内存超限时的优化,以及希望把朴素 DP 改写为凸包、分治、Knuth、单调队列或滚动数组形式的工作流。
限制
资料未说明该技能支持的编程语言、运行环境、依赖安装方式、是否收费、性能保证或失败时的回退策略,这些信息暂未提供。使用时需注意其优化依赖具体递推式是否满足相应前提(如决策单调性、区间 DP 条件等),资料仅给出复杂度变化,未提供具体实现细节与验证方式。