UNIT 01线性依赖
#70 爬楼梯
- 状态定义
- 状态表示到达第 i 级台阶的方案数量。
- 依赖与聚合
- 最后一步来自前一阶或前两阶，两类方案数量相加。
- 基例与顺序
- 起始位置有一种空方案，按台阶递增计算。
- 空间与边界
- 滚动保存最近两态时，先使用旧值再更新。
迁移 · #746 使用最小花费爬楼梯最小花费把方案数求和改为费用取最小，并允许两个免费起点。
先说清契约，再独立实现进入本单元 ↗
第9章｜动态规划
Unit 00 · 状态、重复子问题、依赖顺序与空间压缩前置模型
仅本次页面有效
U00
DP FundamentalsSearch Tree → State DAG → Table
动态规划不是“填表”，
而是把重复未来合并成同一个状态。
本单元用“从位置 0 走到位置 5，每次走 1 或 2 步”的微型实验，亲手经历搜索树膨胀、重复状态识别、记忆化缓存命中、状态依赖排序，以及自底向上的表格计算。
已恢复上次学习位置阶段、动画、答题、代码槽位和迁移进度均已恢复。
本章概念桥｜后续 Unit 会重复使用这些词概念会在动画中出现，不要求先背定义
State
能够完整决定“接下来还要解决什么”的最小信息。
重复子问题
不同历史路径到达同一状态，后续答案完全相同。
Transition
当前状态如何读取更小状态，并聚合为自己的答案。
Base Case
无需继续拆分、可以直接确定答案的最小状态。
Memoization
自顶向下搜索时保存状态答案，重复进入时直接返回。
Tabulation
按照依赖已经完成的顺序，自底向上计算所有状态。
State DAG
合并重复节点后，搜索树变成状态依赖有向无环图。
循环不变量
计算当前状态前，所有被读取的旧状态都已经正确。
统一问题ways(position) = 从当前位置 position 走到 target 的方案数量
只要当前位置相同，剩余可做的选择与未来答案就相同；此前如何到达这里不再影响子问题。
CHAPTER 09 / THE COGNITIVE ATLAS
第 9 章 · 认知梯度全景图
动态规划：定义状态、找出依赖，把重复计算变成有序递推。
贯穿本章的统一框架定义状态的完整含义 → 列出依赖 → 选择求和、最值或布尔聚合 → 按依赖顺序求值。
从基础到复合任务，每一步增加一种决策
这里的梯度描述认知任务的递进，不等同于题库的难度标签。点击题目可进入对应单元。
起点 · Unit 00 动态规划与状态依赖。先理解状态、操作与不变量，再沿下列路线练习。
- 01
- 02
- 03
- 04
每道题在框架中的具体形式
用同一组问题定位每个单元，再观察迁移题改变了哪个条件。进入写代码环节后，学习地图会收起，留出独立思考的空间。
UNIT 02线性依赖
#746 使用最小花费爬楼梯
- 状态定义
- 状态表示到达第 i 个位置所需的最小累计费用。
- 依赖与聚合
- 比较从前一或前两位置支付对应费用后到达的两种成本。
- 基例与顺序
- 两个可直接开始的位置费用为零，依赖按下标递增。
- 空间与边界
- 顶层是数组之外的位置，不能再支付不存在的台阶费。
迁移 · #198 打家劫舍打家劫舍改成选或不选当前房屋，目标从最小成本变成最大收益。
先说清契约，再独立实现进入本单元 ↗
UNIT 03线性依赖
#198 打家劫舍
- 状态定义
- 状态表示考虑前 i 间房屋后的最大合法收益。
- 依赖与聚合
- 比较不选当前房与选择当前房并跳过上一房。
- 基例与顺序
- 空前缀收益为零，按前缀长度递增。
- 空间与边界
- 不能把已经相邻选中的收益当成可读取前驱。
迁移 · #213 打家劫舍 II环形房屋拆成不同时包含首尾的两个线性范围。
先说清契约，再独立实现进入本单元 ↗
UNIT 04线性依赖
#53 最大子数组和
- 状态定义
- 局部状态表示必须以当前位置结尾的最大子数组和。
- 依赖与聚合
- 比较从当前元素重新开始与接上前一位置的最好结尾。
- 基例与顺序
- 从第一个元素初始化，扫描时同时维护全局最大值。
- 空间与边界
- 局部结尾状态不等于全局答案，全负数组仍必须选一个元素。
迁移 · #152 乘积最大子数组最大乘积同时保存最大和最小结尾，负数会翻转大小关系。
先说清契约，再独立实现进入本单元 ↗
UNIT 05容量与选择
#322 零钱兑换
- 状态定义
- 状态表示凑出金额 a 所需的最少硬币数量。
- 依赖与聚合
- 每种可用硬币连接较小金额，选出最少数量并加上当前硬币。
- 基例与顺序
- 金额零需要零个硬币，其余从不可达开始，依赖较小金额。
- 空间与边界
- 硬币可重复使用；不可达状态不能当成有效零数量。
迁移 · #279 完全平方数完全平方数把可选硬币集合改为不超过目标的平方数。
先说清契约，再独立实现进入本单元 ↗
UNIT 06容量与选择
#416 分割等和子集
- 状态定义
- 状态表示处理部分元素后，是否能凑出某个容量。
- 依赖与聚合
- 在不使用与使用当前元素的历史可达性之间做布尔合并。
- 基例与顺序
- 容量零可达；压缩到一维时容量倒序保证每个元素至多使用一次。
- 空间与边界
- 总和为奇数时不可能均分；倒序和正序会改变资源语义。
迁移 · #494 目标和目标和转成选取子集的计数问题，布尔聚合改为数量累加。
先说清契约，再独立实现进入本单元 ↗
UNIT 07容量与选择
#518 零钱兑换 II
- 状态定义
- 状态表示用已经处理的硬币种类凑出金额的组合数量。
- 依赖与聚合
- 加入一种硬币后，累积使用与不使用该种硬币的组合。
- 基例与顺序
- 金额零有一种空组合；硬币外层、金额正序允许重复使用且不计顺序。
- 空间与边界
- 交换两层循环可能变为排列计数，不能机械互换。
迁移 · #377 组合总和 Ⅳ组合总和 IV 让顺序有意义，按总额状态枚举最后选择。
先说清契约，再独立实现进入本单元 ↗
UNIT 08二维位置
#62 不同路径
- 状态定义
- 状态表示到达网格格子的不同路径数量。
- 依赖与聚合
- 上方和左方的路径分别进入当前格，数量相加。
- 基例与顺序
- 起点有一条路径，按行列推进或统一设置第一行与第一列。
- 空间与边界
- 一维压缩中的旧值来自上方，新值来自左方。
迁移 · #63 不同路径 II有障碍格不能传递路径，起点阻塞时所有路径归零。
先说清契约，再独立实现进入本单元 ↗
UNIT 09二维位置
#64 最小路径和
- 状态定义
- 状态表示到达网格格子的最小路径和。
- 依赖与聚合
- 从上方或左方选择较小成本，再加入当前格值。
- 基例与顺序
- 起点为自身值，第一行与第一列只能从单一方向到达。
- 空间与边界
- 不存在的前驱不能当成零成本；滚动更新须区分新旧行。
迁移 · #120 三角形最小路径和三角形的可达邻居和边界形状变化，依赖改成相邻下层位置。
先说清契约，再独立实现进入本单元 ↗
UNIT 10序列关系
#300 最长递增子序列
- 状态定义
- 状态表示必须以第 i 个元素结尾的最长递增子序列长度。
- 依赖与聚合
- 只从之前且数值更小的结尾状态延长，取最大长度。
- 基例与顺序
- 每个元素独立成长度一，按下标从左到右计算。
- 空间与边界
- 要求严格递增，子序列不要求下标连续。
迁移 · #673 最长递增子序列的个数LIS 个数同时维护最优长度和对应数量，等长最优来源需要合计。
先说清契约，再独立实现进入本单元 ↗
UNIT 11序列关系
#1143 最长公共子序列
- 状态定义
- 状态表示两个给定前缀的最长公共子序列长度。
- 依赖与聚合
- 末字符相同时接上双前缀，不同则比较删除一个末字符的两种前缀。
- 基例与顺序
- 空前缀长度为零，按两个前缀长度的依赖顺序求值。
- 空间与边界
- 子序列允许不连续；压缩时保留被覆盖前的对角状态。
迁移 · #718 最长重复子数组最长重复子数组要求连续，状态改为公共后缀，不匹配时归零。
先说清契约，再独立实现进入本单元 ↗
UNIT 12序列关系
#72 编辑距离
- 状态定义
- 状态表示把一个前缀转换为另一个前缀的最少编辑次数。
- 依赖与聚合
- 字符相同时保留，否则比较插入、删除、替换三类前驱成本。
- 基例与顺序
- 空前缀转换费用为另一前缀长度，按前缀依赖顺序计算。
- 空间与边界
- 三个操作读取不同前驱；一维压缩不能丢失旧对角值。
迁移 · #712 两个字符串的最小 ASCII 删除和ASCII 删除和把单位编辑成本改为字符权值，仅保留删除操作。
先说清契约，再独立实现进入本单元 ↗
六段认知流程
本环节已完成
页面不会自动跳转。请停留观察当前状态，确认你能够解释高亮数据。