[!info] related notes

• 相关 MOC:
• 关系笔记:
• 相关资源:

动态规划 MOC

知识总览

filters:
  and:
    - 'file.ext == "md"'
    - 'file.inFolder("z")'
    - 'this.file.links.contains(file)'
    - 'file.path != this.file.path'
formulas:
  knowledge: 'file.asLink(title)'
properties:
  formula.knowledge:
    displayName: 知识
  note.description:
    displayName: Description
  note.mastery:
    displayName: Mastery
views:
  - type: table
    name: 知识总览
    order:
      - formula.knowledge
      - note.description
      - note.mastery
    columnSize:
      formula.knowledge: 280
      note.description: 760
      note.mastery: 56

覆盖范围

本地图负责组织动态规划的学习顺序、题型分组和练习入口。

DP 本身是什么、为什么能工作，统一回到 动态规划；具体题型和模板由各原子笔记承担。

推荐学习顺序

递归
  ↓
暴力搜索
  ↓
重叠子问题
  ↓
记忆化搜索
  ↓
状态定义 / 状态转移
  ↓
自底向上递推
  ↓
题型分类与空间优化

第一阶段：从递归理解 DP

• 递归
• 爬楼梯
• 打家劫舍

练习目标：

同一道题尝试写出暴力递归 → 记忆化搜索 → 递推三个版本。

第二阶段：状态设计

重点区分：

• “前 i 个元素”的前缀型状态；
• “以第 i 个元素结尾”的结束位置状态；
• 二维前缀 / 网格坐标状态。

入口：

• 线性 DP
• 最长递增子序列
• 不同路径
• 最小路径和

第三阶段：背包

• 背包 DP
• 01 背包模板
• 完全背包模板
• 分割等和子集
• 零钱兑换
• 零钱兑换 II
• 目标和

第四阶段：网格与双序列

• 网格 DP 与双序列 DP
• 最长公共子序列
• 编辑距离

第五阶段：区间与状态机

• 区间 DP 与状态机 DP
• 最长回文子串
• 最长回文子序列
• 买卖股票的最佳时机
• 股票含冷冻期
• 股票含手续费
• 股票 k 次交易

第六阶段：进阶分支

• 树形 DP
• 数位 DP
• 概率 DP

每篇题目都按同一组问题复盘

1. 状态表示什么？
2. 转移来自哪些更小状态？
3. 边界 / 初始化是什么？
4. 遍历顺序为什么正确？
5. 是否存在不可达状态？
6. 能否压缩空间？
7. 为什么这道题不是贪心 / 双指针 / 普通 DFS？

掌握路线

能看懂转移
→ 能从递归推导转移
→ 能独立定义状态
→ 能辨别题型
→ 能处理变式
→ 能解释边界和遍历顺序

具体 mastery 统一按 学习中的掌握 评估，不在 MOC 维护第二份评分。