读完这篇，你能做什么
能从小规模枚举推导计数 DP，并说明状态必须包含哪些影响后续结果的信息。
学习理由、准备要求与知识点
为什么学它
回溯与动态规划把递归从语法提升到状态建模，帮助解决组合选择与重复计算。
先读这些内容
知识点清单
- 递归状态与可选动作
- 终止条件与推进
- 选择探索撤销
- 路径快照和剪枝
- 重叠子问题
- 记忆化与表格法
- 状态转移及基础状态
- 枚举输出量与空间优化
运行前先确认Java 17；源码在本机 Microsoft OpenJDK 17.0.20.1 src.zip 核验，在线链接为上游 jdk-17.0.20-ga。深入模块可在掌握基础后回读。
01先弄懂它是什么
遇到“有多少种选法”或“怎样选最省”时，可以先尝试每一种选择。回溯就是选一步、继续试，走不通或试完后撤销，再试别的路。动态规划则保存重复遇到的小问题的答案，减少重复计算，也可以按依赖顺序直接填表。递归只是函数调用自身的写法，回溯和动态规划都不能简单等同于递归。
保存小问题的答案前，要先说明规则：物品能否重复使用、顺序不同算不算新方案，以及要求数量还是最优值。例如固定硬币面额且每种可无限使用时，求最少硬币数只需记录“还差多少钱”；若每枚只能用一次，还要记录已经考虑到哪一枚。记录的信息不够，就可能把不能复用的硬币重复算进去。
动态规划常用到两个性质。一个是能用较小问题的最优答案拼出整个问题的最优答案，叫最优子结构；另一个是计算时会反复遇到同一个小问题，叫重叠子问题。但知道这两个名字，还不等于会填表。你仍要说明每格代表什么、第一格怎样开始、无解怎样记录、先算哪格，以及怎样从结果找回具体方案。先对很小的输入试遍所有选法，再拿来核对表格，往往更容易发现错误。
文中这几个词，先认一认
- 回溯
- 试一个选择，继续搜索，结束或不合适时撤销它，再尝试下一个选择。
- 记忆化
- 把某个小问题算出的答案记下来，下次遇到相同问题就直接使用。
- 状态转移
- 说明当前问题的答案怎样由更小问题的答案算出来。
- 伪多项式
- 例如金额从 1,000 变成 1,000,000，写法只多了三位，按金额逐格建的表却要扩大约一千倍。伪多项式指运行量按输入数值的大小衡量是多项式级、按写下输入所需的位数衡量却未必如此，不能把“输入写得短”当成“计算量小”。
02看看它怎么工作
回溯要同时维护当前选择与可行性边界。若使用同一个可变路径列表，递归进入前 add，返回后 remove，保存答案时复制当前路径；否则所有结果可能共享同一个最后被清空的列表。剪枝只能排除已证明不可能产生目标答案的分支，不能为了快随意跳过尚未证伪的选择。
记忆化把“同一个小问题反复算”改成“算一次，以后查记录”。缓存键若漏掉会影响答案的条件，就会把不同问题混成一个；若塞进无关历史，又会错过复用机会。计算依赖没有环时，可以按先完成依赖、再处理当前项的顺序填表。遇到循环依赖或负权等情况，需要根据具体问题选择方法，不能盲目套一层 for 循环。
求最少硬币数时，best[a] 表示凑出金额 a 最少需要几枚。最后选一枚面额 c 的硬币，就还要凑出 a-c，因此候选答案是 best[a-c]+1；在合法面额中取最小值。best[0]=0，因为凑零元不需要硬币；凑不出的金额用专门数值标记，并跳过这些无解候选。所有面额都为正，所以从小金额算到大金额时，前面的答案已经准备好。再记下是哪枚硬币改善了答案，就能从总额往回找到一条方案。
正在加载流程图…
查看流程图源码（Mermaid）
flowchart TD
A["明确选择能否重复及优化目标"] --> B["定义状态：金额 a 的最少硬币数"]
B --> C["基础状态 best0=0"]
C --> D["按金额从小到大"]
D --> E["枚举最后一枚面额 c"]
E --> F["比较 best[a-c]+1"]
F --> G["记录更优值与前驱面额"]
G --> H["从目标金额恢复方案"]按顺序看，每一步做了什么
- 先确定选择、重复与答案类型。
- 写出包含全部相关条件的状态。
- 定义基础和不可达状态。
- 证明转移与计算顺序正确。
- 恢复方案并用小例子核对最优性。
03对照实现代码
Microsoft OpenJDK 17.0.20.1；java.base/java/util/regex/Pattern.java · java.util.regex.Pattern$Branch#match(Matcher,int,CharSequence)
以下为原创 Java 17 教学实现，不是原样 JDK 源码；只保留文中明确讨论的机制，省略优化、兼容及内部接口。
public final class SourceModel {
public static boolean subset(int[] values, long target) {
return choose(values,0,0L,target);
}
private static boolean choose(int[] values, int index, long sum, long target) {
if (index == values.length) return sum == target;
// 先尝试选择当前元素，失败后再尝试不选。
if (choose(values,index+1,Math.addExact(sum,values[index]),target)) return true;
return choose(values,index+1,sum,target);
}
}真实 Pattern 的 Branch 节点遍历候选节点并尝试匹配，某条分支成功时返回，失败后继续其它分支。模型改用子集选择展示“尝试一条路径，失败再换另一条”的控制思想，不模拟正则字符规则、捕获组、量词或匹配状态，也不声称 JDK 正则实现了本篇硬币动态规划。
分支节点只是完整匹配引擎的一部分，状态保存和回退可能由其它节点协作处理，不能把几行候选循环当成全部正则语义。教学模型把 index 与 sum 作为递归值参数，因此无需修改后撤销共享路径；若收集具体选择列表，则需要显式恢复状态。
每个元素选或不选产生两个方向，最坏可能探索指数数量路径。短路找到一个可行解时可以提前结束，但这只是某些输入的更早返回，不改变最坏界。真实正则的成本取决于模式和输入，某些回溯组合也可能产生大量尝试，不能笼统宣称所有匹配都线性。
不同递归路径若到达相同 index 和 sum，而且后面可选元素也相同，就可以保存并复用这一状态的结果。只按 sum 缓存却不记录 index，会把剩余可选元素不同的情况混起来，破坏每个元素最多选一次的规则。这个例子帮助连接分支搜索与结果复用，具体问题能否用动态规划仍需重新分析。
代码先调用谁，再调用谁
- Pattern 匹配引擎进入 Branch 节点
- 依次选择候选节点路径
- 调用候选 match 并在成功时返回
- 失败继续下一分支，完整状态行为由其它匹配节点协作
04动手写一个例子
最少硬币数量与一条最优方案
面额为正整数且可无限重复，目标金额零到一百万。返回最少硬币数与一条方案；无法组成返回 Optional.empty。重复面额先去重，负目标或非正面额拒绝。
- 输入 1
面额[1,3,4]，金额6- 输出 1
2枚，[3,3]
- 输入 2
面额[2]，金额3- 输出 2
无解
- 输入 3
金额0- 输出 3
0枚，空方案
贪心每次选最大面额对任意面额集合并不正确，例如六使用四、一、一要三枚，三、三只需两枚。动态规划考虑最后一枚硬币的全部合法选择，只要子金额已得到最优值，就能比较所有可能的完整方案，不依赖面额具有特殊货币性质。
不可达哨兵设为 amount+1，因为若存在解，正整数面额下最多需要 amount 枚一单位硬币的量级，任何更大值都可代表暂未可达。更新前检查子状态可达，避免把哨兵参与运算当成真实方案。面额排序后超过当前金额即可停止枚举。
记录 lastCoin[a] 表示改善 best[a] 时选择的最后一枚。恢复时不断减去这个正面额，金额严格下降直到零，因此不会形成回溯环。平价时保持先遇到的面额，结果确定但不宣称在所有最优方案中还满足其它字典序目标；额外平价目标需要进入状态或比较规则。
为什么这样写是对的计算金额 a 之前，所有更小金额的 best 已是最优或明确不可达；lastCoin 只指向严格更小的可达金额。
每个金额最多枚举 k 个面额，预处理排序去重；复杂度按数值 A 增长而非 log A，因此称为伪多项式，不适合无上限的大金额。
保存为 Main.java，运行 javac --release 17 -encoding UTF-8 Main.java，再运行 java Main。程序包含固定输入自测，断言失败时会抛出错误。
展开收起代码 · Main.java · 完整可运行程序
长行可在代码区域内左右滚动，按 Tab 可把焦点移入代码区。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
public class Main {
record Plan(int count, List<Integer> coins) {}
static Optional<Plan> solve(int[] input, int amount) {
if (input == null || amount < 0 || amount > 1_000_000)
throw new IllegalArgumentException("input");
for (int coin : input) if (coin <= 0) throw new IllegalArgumentException("coin");
int[] coins = Arrays.stream(input).distinct().sorted().toArray();
int unreachable = amount + 1;
int[] best = new int[amount+1], lastCoin = new int[amount+1];
Arrays.fill(best,unreachable);
best[0] = 0; // 空金额的基础状态，不能初始化所有位置为零。
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin > a) break;
if (best[a-coin] != unreachable && best[a-coin]+1 < best[a]) {
best[a] = best[a-coin]+1;
lastCoin[a] = coin;
}
}
}
if (best[amount] == unreachable) return Optional.empty();
List<Integer> chosen = new ArrayList<>();
for (int left = amount; left > 0; left -= lastCoin[left])
chosen.add(lastCoin[left]); // 正面额保证恢复路径严格下降。
return Optional.of(new Plan(best[amount],List.copyOf(chosen)));
}
static void require(boolean condition) {
if (!condition) throw new AssertionError();
}
public static void main(String[] args) {
// 贪心反例、不可达、零金额、重复面额和单面额。
require(solve(new int[]{1,3,4},6).equals(Optional.of(new Plan(2,List.of(3,3)))));
require(solve(new int[]{2},3).isEmpty());
require(solve(new int[]{},0).equals(Optional.of(new Plan(0,List.of()))));
require(solve(new int[]{1,1,3},6).get().count() == 2);
require(solve(new int[]{5},20).get().coins().equals(List.of(5,5,5,5)));
require(solve(new int[]{},1).isEmpty());
boolean rejected = false;
try { solve(new int[]{0,1},2); } catch (IllegalArgumentException e) { rejected = true; }
require(rejected);
System.out.println("PASS 7");
}
}这些特殊情况也要试一试
- 零目标有空方案，即使面额集合为空。
- 正目标与空面额无解。
- 零或负面额拒绝，避免无进展状态。
- 重复面额不改变最优结果。
进阶选读 · 可选深入：零一背包与方案计数
场景每件物品只能用一次，或需要计算所有不同组合数量。
做法零一状态要包含位置或采用正确逆序容量遍历；组合与排列计数的循环顺序不同，计数还可能需要 BigInteger。
复杂度常见背包 O(nA)，计数值大小和输出方案数量会增加成本。
好处与代价状态压缩节省空间却更易写错依赖方向，先保留二维参考实现验证语义。
05项目里怎么用
动态规划首先是建模问题。输入约束、是否重复使用、优化目标和不可达含义必须明确，错误状态即使运行很快也没有价值。可以对小输入写穷举参考方法，与 DP 批量比较；参考算法慢但范围受控，能帮助发现转移与初始化错误。
资源限制要与状态维度绑定。一百万金额是一维表的明确边界，若再乘物品数、时间或位置，内存可能快速增长；稀疏记忆化也可能在最坏情况下访问全部状态。不能把使用 Map 缓存当成天然节省空间，应该估算可能状态数与键成本。
用回溯或正则处理外部输入时，先估算最坏可能尝试多少次，以及如何停止。限制输入长度、选择合适算法或简化模式，通常比线程卡住后再补救更可靠。跳过分支必须确定不会漏解，缓存必须记录完整条件并及时失效，避免复用错答案或过期结果。
容易踩的坑
- 贪心在一个样例成立就当作任意面额最优。
- 缓存键漏掉可选位置或其它相关条件。
- 所有 DP 状态初始化为零，混淆不可达。
- 回溯保存同一个可变路径引用而不复制。
几种做法，怎么选
表格有四列，窄屏可左右滑动查看代价和适用条件。
| 方案 | 优势 | 代价与限制 | 适用条件 |
|---|---|---|---|
| 回溯穷举 | 规则表达直接且能枚举方案 | 最坏搜索量可能指数增长 | 小规模、约束强或参考验证 |
| 记忆化递归 | 按需访问状态且贴近递推 | 栈深与缓存键成本需要管理 | 状态稀疏或依赖自然递归 |
| 迭代表格 | 计算顺序与资源范围明确 | 可能计算不需要的状态 | 状态空间适中且依赖有序 |
06检验是否读懂了
先自己想、自己写，再展开答案核对。场景题是假设的练习情境；遇到还没学过的内容，可以做完基础后再回来。
先用自己的话解释
01递归是否就是动态规划？
展开参考答案与推导
不是。递归只描述调用自身的控制方式，可能大量重复计算；动态规划通过正确状态与保存结果复用子问题，也可以完全使用循环填表。两者关系取决于是否利用了重叠状态。
02为什么本题复杂度称伪多项式？
展开参考答案与推导
表格大小取决于金额数值 A，而输入表示 A 只需约 log A 位。对编码长度而言 A 可能非常大，因此 O(Ak) 不等于对所有输入长度都是普通多项式高效。
03零面额为什么必须拒绝？
展开参考答案与推导
它不能使剩余金额减少，会破坏递归终止或方案恢复的严格进展，转移也可能引用自身。题目要求正面额正是为了建立向更小状态的无环依赖。
换个情况，还会处理吗
01贪心给三枚，DP给两枚，谁错了？
展开参考答案与推导
先看面额是否具备贪心正确性条件。对一、三、四组成六，三加三比四加一加一更优，说明最大优先的局部选择不能保证任意面额全局最优。
02记忆化结果偶尔复用错，先检查什么？
展开参考答案与推导
检查缓存键是否包含所有影响后续选择的状态，以及不同输入面额集合是否共享了未失效缓存。只缓存剩余金额可能适合固定无限面额问题，却不适合剩余物品集合变化的零一问题。
03回溯输出最后全是空列表，为什么？
展开参考答案与推导
很可能把同一个 path 引用加入结果，然后回溯 remove 清空它。保存答案时应复制当前路径容器；如果元素也可变，还需根据结果契约决定复制深度。
写代码试一试
01验证方案合计等于目标
- 输入 / 条件
面额[1,3,4]，金额6- 输出 / 预期
方案和6且长度2
提示 最优数值之外验证恢复。
展开参考答案与推导
对返回 coins 求和并比较目标，再比较列表长度与 count。DP 数量正确并不自动证明前驱记录与恢复循环正确，两类断言应同时存在。
02加入一种不影响答案的大面额
- 输入 / 条件
[1,3,4,100]，金额6- 输出 / 预期
仍为2枚
提示 超过当前金额的面额跳过。
展开参考答案与推导
追加一百后结果应保持原最优值，排序使枚举遇到超限即可停止。该测试也说明面额数量和可用范围影响实际工作，但不改变最坏复杂度上界。
03改为每枚面额只能用一次
- 输入 / 条件
面额[3]，目标6- 输出 / 预期
无解
提示 状态必须限制重复选择。
展开参考答案与推导
使用物品位置与金额的二维状态，或一维容量从大到小更新，确保当前物品不会在同一轮被重复使用。直接沿用本题从小到大金额转移会错误地把一枚三用两次。
读完之后，独立完成
课后作业：自己做一遍
本篇共 10 道作业，先完成 8 道基础与综合任务，再按前置知识挑战进阶题。其中包含 1 道思维拓展，试着换个条件，看看原来的办法是否还管用。不附参考答案。
能从小规模枚举推导计数 DP，并说明状态必须包含哪些影响后续结果的信息。
本篇重点加练
重点强化状态定义与转移完整性，避免程序速度提高后却缓存或合并了不同问题。
- 递归状态与可选动作
- 状态转移及基础状态
重点内容会多练几次。先说清楚怎么做，再试试空数据、出错或条件改变时会发生什么。
先自己做，卡住时记下问题，再回来查。问答题写清“为什么、什么时候适用”；动手题留下输入、输出和运行步骤，方便下次重做。
基础必做
- 作业 01原理问答
求由数字 1、2 构成且总和为 4 的所有有序选择序列。定义递归状态、可选动作、成功条件和失败条件，画出搜索树的一部分并说明推进依据。
- 提交内容
- 状态定义和搜索树。
- 怎样算完成
- 序列与无序组合合同分开
- 所有分支有终止论证
练到的知识点递归状态与可选动作 · 终止条件与推进
- 作业 02排错实验
编写保存当前路径的回溯实验，分别保存同一个列表引用与保存独立路径数据；结束后检查各结果对象的身份和内容。再提出一项剪枝并证明不会漏掉合法结果。
- 提交内容
- Java 实验、自写路径独立性测试、剪枝论证和运行记录。
- 怎样算完成
- 选择与撤销对称
- 剪枝正确性不以速度代替
练到的知识点选择探索撤销 · 路径快照和剪枝
综合应用
- 作业 03代码推演
对爬楼梯问题以 6 级为输入，画出朴素递归中重复状态，再分别说明记忆化与自底向上表格如何安排计算；写明缓存键包含什么。
- 提交内容
- 递归/状态图与求值顺序。
- 怎样算完成
- 相同状态判据完整
- 缓存成本和递归栈分别考虑
练到的知识点重叠子问题 · 记忆化与表格法
- 作业 04编程实践
实现带禁用台阶的爬楼梯计数，每次走 1 或 2 级，输入 n=6、禁用集合 {3}；定义起点、终点被禁用和计数溢出的政策，同时提供小规模穷举参考。
- 提交内容
- Java 实现、自写边界及交叉验证测试、运行证据。
- 怎样算完成
- 基础状态遵守业务合同
- 转移不读取未定义状态
- 计数范围有处理
练到的知识点状态转移及基础状态 · 枚举输出量与空间优化
- 作业 05面试场景
订单优惠搜索中，同一金额却拥有不同剩余优惠券。团队只按金额缓存，结果速度快但偶尔错误。设计区分状态的反例与修复后的资源评估。
- 提交内容
- 状态反例、缓存键合同和复杂度分析。
- 怎样算完成
- 缓存键包含影响后续决策的信息
- 正确性与状态空间权衡明确
练到的知识点递归状态与可选动作 · 路径快照和剪枝 · 重叠子问题 · 枚举输出量与空间优化
- 作业 06编程实践
实现最长不连续选课时长：每天可选一个课时但不能连续两天选，输入可含零时长；先定义状态和返回合同，再与小规模穷举比较。
- 提交内容
- Java 实现、自写空输入/平价/边界测试及运行证据。
- 怎样算完成
- 状态包含决策所需信息
- 转移与基础状态可独立解释
练到的知识点递归状态与可选动作 · 状态转移及基础状态
- 作业 07设计评审
旅行计划既要限制总预算又要限制剩余天数，团队只把预算作为缓存键。写出两段可能到达相同预算的历史，审查它们的未来动作是否相同。
- 提交内容
- 状态候选、历史样本和等价判定。
- 怎样算完成
- 状态相同的依据可检验
- 不必要历史与必要条件分别讨论
练到的知识点递归状态与可选动作
- 作业 08代码推演
任务每天可休息或执行，连续执行最多两天。只写状态定义、基础状态和 n=3 的手工转移表，不急于压缩空间。
- 提交内容
- 状态转移表和完整动作检查。
- 怎样算完成
- 合法动作与失败状态均覆盖
- 计算顺序满足依赖关系
练到的知识点状态转移及基础状态
进阶挑战 · 掌握前置后选做
- 作业 09编程实践
完成二维 DP 后：实现每件最多一次的背包最优价值，并恢复一条选中物品方案；测试零容量、零价值、重复重量和多个最优解，明确多个方案同样最优时如何选择。
- 提交内容
- Java 实现、自写小规模穷举对照和边界测试、运行证据。
- 怎样算完成
- 每件使用次数有验证
- 恢复方案满足容量与价值
- 空间优化前后语义一致
练到的知识点记忆化与表格法 · 状态转移及基础状态 · 枚举输出量与空间优化
思维拓展
先写出你的猜想，再用例子或实验验证。答案可以不同，但要说清依据、适用情况，以及还有什么没弄懂。
- 作业 10思维拓展 · 条件变化
选课优化从“最大总时长”改为“先达到最低学分，再最小化总时长”。比较原状态和目标是否足够，并设计能区分两目标的输入。
- 提交内容
- 目标比较、状态修订及验收样本。
- 怎样算完成
- 优化目标与可行性约束分开
- 修订由具体反例或论证支持
练到的知识点递归状态与可选动作 · 状态转移及基础状态
完成后，再检验一次
给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题，记下卡在哪里。隔一天换一组输入再试，能解释结果和出错原因，再把这个知识点标为掌握。
继续阅读
先看能帮你完成当前练习的部分。例子跑通后，再读更深入的解释。
- 必读教程英文
Illinois Algorithms：回溯章节 （新标签页）↗
阅读逐步构造解、枚举分支、约束与剪枝；先掌握递归和基本结构，再阅读完整推导。
- 实践教程英文
Illinois Algorithms：动态规划章节 （新标签页）↗
阅读重叠子问题、记忆化、状态转移与计算顺序，比较搜索树与状态图。
- 深入教程英文
MIT 6.006：递归算法与动态规划 （新标签页）↗
阅读第十五讲的子问题、递推式、拓扑顺序和基础情形方法，练习从递归转换到 DP。
- 深入教程英文
Harvard CS50：算法 （新标签页）↗
阅读线性/二分查找、排序与 O/Ω/Θ，跟随具体输入推导操作次数。
- 深入参考文档英文
OpenJDK 17u java.util.regex.Pattern$Branch （新标签页）↗
定位
Pattern.Branch.match的候选路径尝试，模型仅展示回溯分支控制，不把正则引擎冒称硬币 DP 源码。