动态规划优化器Skill dp-optimizer

---

name: dp-optimizer description: 自动应用高级动态规划优化 allowed-tools:

• Read
• Write
• Grep
• Glob
• Edit

---

DP优化器技能

目的

应用高级动态规划优化技术，以改进动态规划解决方案的时间和空间复杂度。

能力

• 凸包技巧检测与应用
• 分治优化
• 克努斯优化
• 单调队列/双端队列优化
• 外星人技巧 / WQS二分搜索
• 滚动数组优化
• 位掩码压缩

目标流程

• dp状态优化
• 高级动态规划技术
• 复杂度优化

优化技术

时间优化

1. 凸包技巧：对于特定递推关系，复杂度从 O(n^2) 降至 O(n log n)
2. 分治优化：当最优分割点具有单调性时，复杂度从 O(n^2 k) 降至 O(n k log n)
3. 克努斯优化：对于特定区间动态规划，复杂度从 O(n^3) 降至 O(n^2)
4. 单调队列：对于滑动窗口动态规划，复杂度从 O(n*k) 降至 O(n)

空间优化

1. 滚动数组：当仅需要前一行数据时，空间复杂度从 O(n*m) 降至 O(m)
2. 位掩码压缩：通过位操作减少状态空间

输入模式

{
  "type": "object",
  "properties": {
    "dpCode": { "type": "string" },
    "stateDefinition": { "type": "string" },
    "transitions": { "type": "string" },
    "currentComplexity": { "type": "string" },
    "targetComplexity": { "type": "string" },
    "optimizationType": {
      "type": "string",
      "enum": ["auto", "convexHull", "divideConquer", "knuth", "monotonic", "space"]
    }
  },
  "required": ["dpCode", "optimizationType"]
}

输出模式

{
  "type": "object",
  "properties": {
    "success": { "type": "boolean" },
    "optimizedCode": { "type": "string" },
    "optimizationApplied": { "type": "string" },
    "newComplexity": { "type": "string" },
    "explanation": { "type": "string" }
  },
  "required": ["success"]
}