---

名称: dp-模式库 描述: 维护并匹配经典动态规划模式库。为DP问题提供模式匹配、模板代码生成、变体检测和问题到模式的映射。 允许工具: Bash, Read, Write, Grep, Glob, WebSearch 元数据: 作者: babysitter-sdk 版本: “1.0” 类别: 算法优化 技能ID: SK-ALGO-012 优先级: 高

dp-模式库

一个专门用于动态规划模式识别的技能，将问题匹配到已知的DP模式，生成模板代码，并为DP解决方案提供优化指导。

目的

通过以下方式协助动态规划：

• 将问题匹配到50多种经典DP模式
• 为匹配的模式生成模板代码
• 检测问题变体（背包问题变体、LCS变体等）
• 提供状态设计建议
• 建议优化技术

能力

核心功能

1. 模式识别

   • 分析问题描述以寻找DP指标
   • 匹配到已知的模式类别
   • 识别问题变体和转换
   • 建议状态表示

2. 模式类别

   • 线性DP（一维数组）
   • 网格/矩阵DP（二维路径）
   • 字符串DP（LCS，编辑距离）
   • 区间DP（范围，括号化）
   • 树形DP（子树问题）
   • 位掩码DP（子集枚举）
   • 数位DP（数字计数）
   • 背包问题变体
   • 带状态机的DP

3. 代码生成

   • 为识别出的模式生成模板代码
   • 支持多种语言（Python, C++, Java）
   • 解释状态和转移的注释
   • 空间优化变体

4. 优化指导

   • 滚动数组技术
   • 凸包优化
   • 分治优化
   • 单调队列/栈优化
   • Knuth优化

模式库

线性DP模式

模式	状态	转移	示例问题
斐波那契	dp[i] = 位置i的答案	dp[i] = dp[i-1] + dp[i-2]	爬楼梯，打家劫舍
最小/最大路径	dp[i] = 以i结尾的最佳答案	dp[i] = opt(dp[j]) + cost(j,i)	最小路径和
计数	dp[i] = 到达状态i的方法数	dp[i] = sum(dp[j])	不同路径，解码方法
最长递增子序列	dp[i] = 以i结尾的LIS长度	dp[i] = max(dp[j]) + 1 其中 j < i, a[j] < a[i]	最长递增子序列

字符串DP模式

模式	状态	示例问题
编辑距离	dp[i][j] = s1[0…i], s2[0…j]的距离	编辑距离，一次编辑距离
最长公共子序列	dp[i][j] = s1[0…i], s2[0…j]的LCS	最长公共子序列
回文串	dp[i][j] = s[i…j]是否是回文串	最长回文子串
正则表达式匹配	dp[i][j] = s[0…i]是否匹配p[0…j]	正则表达式匹配

背包模式

变体	状态	转移
0/1背包	dp[i][w] = 使用物品0…i，容量w的最大价值	dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
完全背包	dp[w] = 容量w的最大价值	dp[w] = max(dp[w], dp[w-wt[i]] + val[i])
多重背包	dp[i][w] = 有限物品的最大价值	使用二进制表示或双端队列
子集和	dp[i][s] = 是否能用物品0…i达到和s	dp[i][s] = dp[i-1][s] 或 dp[i-1][s-a[i]]

网格DP模式

模式	状态	示例问题
路径计数	dp[i][j] = 到达(i,j)的方法数	不同路径，不同路径II
路径最小/最大	dp[i][j] = 到达(i,j)的最佳路径	最小路径和
多路径	dp[i][j][k][l] = 两条路径同时进行	摘樱桃

区间DP模式

模式	状态	示例问题
矩阵链乘法	dp[i][j] = 范围[i,j]的成本	矩阵链乘法
戳气球	dp[i][j] = 气球[i…j]的最大硬币数	戳气球
合并	dp[i][j] = 合并范围[i,j]的成本	合并石头的最低成本

树形DP模式

模式	状态	示例问题
子树	dp[v] = 以v为根的子树的答案	二叉树中的最大路径和
换根	dp[v] = 当v是根时的答案	树中距离之和
父子约束	dp[v][0/1] = 带约束的答案	打家劫舍III

位掩码DP模式

模式	状态	示例问题
旅行商问题	dp[mask][last] = 访问mask城市，以last结束的最小成本	旅行商问题
任务分配	dp[mask] = 将任务分配给子集的最小成本	任务分配
子集和	dp[mask] = 子集的和	子集和

使用方法

模式匹配

# 将问题匹配到DP模式
dp-模式库 匹配 --问题 "给定一个整数数组，找到最长递增子序列"

# 输出:
# 模式: 线性DP - 最长递增子序列 (LIS)
# 状态: dp[i] = 以索引i结尾的LIS长度
# 转移: dp[i] = max(dp[j] + 1) 对所有 j < i 且 arr[j] < arr[i]
# 时间: O(n^2) 朴素, O(n log n) 使用二分查找
# 空间: O(n)

模板生成

# 生成模板代码
dp-模式库 模板 --模式 "lis" --语言 python

# 输出:
def lengthOfLIS(nums):
    if not nums:
        return 0

    n = len(nums)
    # dp[i] = 以索引i结尾的LIS长度
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

优化建议

# 获取优化建议
dp-模式库 优化 --模式 "lis"

# 输出:
# 当前: O(n^2) 时间, O(n) 空间
# 优化:
# 1. 二分查找: O(n log n) 时间
#    - 维护最小尾部元素的有序列表
#    - 二分查找插入点
# 2. 线段树: O(n log n) 时间
#    - 用于坐标压缩 + 范围最大值查询

输出模式

{
  "匹配": {
    "模式": "线性DP - LIS",
    "置信度": 0.95,
    "类别": "线性",
    "变体": ["LIS", "LDS", "LNDS"]
  },
  "状态": {
    "描述": "dp[i] = 以索引i结尾的LIS长度",
    "维度": 1,
    "含义": "以位置i结尾的LIS长度"
  },
  "转移": {
    "公式": "dp[i] = max(dp[j] + 1) 对 j < i, arr[j] < arr[i]",
    "基础情况": "dp[i] = 1 对所有 i",
    "顺序": "从左到右"
  },
  "复杂度": {
    "时间": "O(n^2)",
    "空间": "O(n)",
    "优化后": {
      "时间": "O(n log n)",
      "技术": "耐心排序上的二分查找"
    }
  },
  "模板": {
    "python": "...",
    "cpp": "...",
    "java": "..."
  },
  "类似问题": [
    "最长递增子序列",
    "最长递增子序列的个数",
    "俄罗斯套娃信封问题",
    "最长数对链"
  ]
}

与流程集成

此技能增强：

• dp-模式匹配 - 核心模式匹配工作流
• dp-状态优化 - 状态空间优化
• dp-转移推导 - 推导转移方程
• leetcode-问题解决 - DP问题识别
• 经典dp库 - 构建个人DP库

模式识别指标

指标	可能的模式
“最大/最小” + “子数组/子序列”	线性DP
“方法数”	计数DP
“能否达到/实现”	布尔DP
“编辑/转换字符串”	字符串DP
“合并/组合区间”	区间DP
“树/子树”	树形DP
“选择子集” + 小的n	位掩码DP
“计数具有属性的数字”	数位DP
“物品 + 容量”	背包

参考

• 动态规划模式
• DP可视化工具
• LeetCode DP模式
• CP算法 - DP
• CSES DP部分

错误处理

错误	原因	解决方案
无模式匹配	问题不符合已知模式	考虑贪心或其他方法
模糊匹配	多个模式可能适用	提供更多问题细节
复杂状态	状态过于复杂，不适合模板	需要手动状态设计

最佳实践

1. 从暴力开始 - 在优化前理解递推关系
2. 绘制状态图 - 可视化转移
3. 验证基础情况 - 大多数DP错误在基础情况中
4. 检查状态唯一性 - 每个状态应被唯一定义
5. 考虑空间优化 - 通常可以减少维度
6. 用小输入测试 - 手动跟踪