LOOP 07 / INTERVIEW LOOP / 4H
动态规划：先写状态的含义，再谈优化
一次任务需要用若干批次凑出目标数量。贪心地选最大批次看起来很自然，但你要主动找到它失败的输入，并用状态定义保证递推只依赖已知答案。
完成单元 52 · 用主项目回答一个性能问题及其先备后安排本次训练。不绑定日历周。
先写自己的答案，再展开参考。这里按技能编写问题，不声称公司真题；自评与阅读都不会自动通过 G0。
先备与学习位置
TIME WITH OUTPUTS
240 分钟怎样用
闭卷恢复先备 · 15min
用一句话定义 DP 状态、不可达和基例；复述第26章正确性先于测量、样本与结论的区别。
留下：先不查章节，写三条判断和一个不确定点；再只补读相关章节的解释段。
澄清题目与手算 · 25min
读主问题，逐条写输入、输出、范围与失败行为。手算前两个公开用例，给自己的方案找一个反例。
留下：一份接口合同、逐步状态表和最小反例；不要先打开参考推演。
独立实现或设计 · 55min
实现 min_batches(coins,amount)：每种正整数批次可无限使用，求精确凑成 amount 的最少批次数，不可达返回 -1。coins 最多 8 项、每项 1..20，amount 在 0..50。先写一维动态规划，并解释为什么不是直接选最大值。
留下：保存个人代码或设计稿。编码题保留编译命令；设计题为每个事件编号，不能只画没有状态的箭头。
边界与反证 · 25min
用题目的全部公开用例核对真实输出；另外创造一个与公开输入不同的边界。发现失败时缩小输入，再解释修复。
留下：实际结果、原始失败和修复原因各一份；设计题记录一个被拒绝的执行顺序。
按表现进入追问树 · 35min
从 n1 开始。每题先录下自己的回答，再展开标准；按满足或未满足条件跳转。树最多走一轮，卡住时把剩余时间用于分支中的纠错，不循环加时。
留下：记录经过的节点、原话、缺失条件和修订；只会复述标准的节点仍标记待重做。
英文口述与打断 · 30min
用本页英文提纲录制两轮 90 秒回答；第二轮在 30 秒处自问追问，先回答追问再回到主线。每轮回听并改写两个含糊句。
留下：两轮录音或逐字稿；圈出输入、因果、边界和限制各一句。参考英文在录完第一轮后再读。
复盘与安排重做 · 25min
对照强弱答案，选择一个真正出错的环节：合同、状态、实现、验证或表达。填本页记录模板，并约定下一天的 30 分钟。
留下：一个有失败输入的错误记录和一个可观察修复标准；不要把全部问题归因为粗心。
次日无答案重做 · 30min
次日用相同状态思路处理 coins=[3,5]，独立求 amount=0、4、8、9、10，并写 dp[0..10]；不能只列出看起来能凑的组合。
留下：这是本周 240 分钟中的最后 30 分钟，不另加预算。先关闭解答，用 20 分钟独立做，再用 10 分钟核验并记录是否仍需复习。
包括次日重做，总计 240min。局部错因复盘属于本次练习，额外的计划复盘按实际需要另记。
SOLVE BEFORE READING THE ANSWER
先独立处理这个问题
实现 min_batches(coins,amount)：每种正整数批次可无限使用，求精确凑成 amount 的最少批次数，不可达返回 -1。coins 最多 8 项、每项 1..20，amount 在 0..50。先写一维动态规划，并解释为什么不是直接选最大值。
输入与输出合同
- 只要求最少数量，不要求恢复具体组合；重复的批次大小不影响答案。
- amount=0 返回 0，即使 coins 为空；正数目标配空 coins 返回 -1。
- 本练习输入保证范围合法；若要扩展生产接口，须另定义非法面值 0、负值和极大输入的拒绝方式。
手算之后，对照公开用例
| 输入或情形 | 预期 | 为什么 |
|---|---|---|
| coins=[1,3,4], amount=6 | 2 | 3+3；贪心 4+1+1 得 3 次，不最优。 |
| coins=[2,4], amount=3 | -1 | 目标不可达。 |
| coins=[], amount=0 | 0 | 空组合凑成 0。 |
| coins=[], amount=5 | -1 | 没有可用批次。 |
| coins=[2,2,3], amount=7 | 3 | 2+2+3；重复面值不改变最少次数。 |
先保留自己的解法、状态轨迹与验证记录，再打开参考。允许用自然语言或伪代码补充解释；不能用参考输出代替真实运行。
保存独立尝试后，阅读解法与状态轨迹
解法依据
dp[x] 表示精确凑成 x 的最少次数。设 dp[0]=0，其余设为 amount+1 作为不可达标记。按 x 从 1 到 amount 递增，对每个 c≤x 且 dp[x-c] 可达的面值，尝试 dp[x-c]+1。只依赖更小金额，因为 c>0。返回 dp[amount]，若仍不可达则返回 -1。时间 O(amount×面值数量)，空间 O(amount)。这是有界输入下的算法题，不是测得的 CPU 加速结果。
逐步推演
[1,3,4] 的 dp[0..6] 为 [0,1,2,1,1,2,2]。算 dp[6] 时：用 1 得 dp[5]+1=3，用 3 得 dp[3]+1=2，用 4 得 dp[2]+1=3，选 2。每个候选都对应最后一次选择，覆盖了所有合法解的结尾。
FOLLOW THE ANSWER, NOT A SCRIPT
从回答进入下一层追问
从 n1 开始。先录下回答，再展开判定；达到条件就走深入分支，未达到就按反馈缩小问题。一次最多走一轮，不靠反复查看同一答案累积“通过”。
NODE n1
为什么 4+1+1 不能证明最少？
NODE r1
把第一个追问缩到最小输入，重新逐步说明。
我已作答：查看判定与下一分支
需要解释清楚：它只是一组可行解；3+3 用更少次数，是反驳贪心最优性的具体证据。
NODE n2
允许面值 0 时，递推的哪个前提消失？
NODE n3
把每个 x 分配给不同线程同时计算，可以直接更快吗？
我已作答：查看判定与下一分支
需要解释清楚：不行，dp[x] 依赖若干更小 x；无依赖管理会读取尚未计算结果。需要先分析 DAG 与开销，不能根据线程数量宣布加速。
达到
结论正确，并解释本节点给出的具体状态或反例。
保留关键推理：不行，dp[x] 依赖若干更小 x；无依赖管理会读取尚未计算结果。需要先分析 DAG 与开销，不能根据线程数量宣布加速。
这一分支结束：对照并复盘 →答案强在哪里，弱在哪里
保存自己的回答后，打开对照
弱答案
“每次拿最大批次就最少；DP 就是把答案存起来。”
强答案
“最大批次策略在 1、3、4 凑 6 时失败。我的 dp[x] 是精确凑成 x 的最少次数，枚举最后一个批次，因此每个最优解都被某个候选覆盖。正面值保证依赖更小状态，不可达状态不会参与加一。”
强答案明确状态、基例、转移和依赖顺序，并用反例选择算法。能背出递推式但不能解释 x 的含义，仍容易把精确凑成误写成至少凑成。
在自己的原回答里划出一个缺失的条件或错误推理，再重说一遍。完整句子背熟，不代表能处理新约束。
ANSWER, THEN HANDLE AN INTERRUPTION
英文口述与打断
Defend your state definition and give a counterexample to greediness.
- Define exact amount, not at least amount.
- Explain the last-choice argument.
- Separate algorithmic complexity from measured speed.
“Why can’t you calculate all table entries in parallel?”
录完第一轮后，读英文示范
The state stores the minimum number of batches needed for an exact amount. I consider every possible final batch and combine it with a solved smaller state. Greedy selection fails for sizes one, three, and four when the target is six. The table gives a time bound, but it does not by itself establish a measured speedup.- 前 15 秒说明输入、输出和一个关键约定。
- 至少用一个本题的数值解释因果，不只罗列英文术语。
- 明确一个边界或尚未验证的限制；不能把教学推演说成项目经验。
次日关掉解答，换一个问题
次日用相同状态思路处理 coins=[3,5]，独立求 amount=0、4、8、9、10，并写 dp[0..10]；不能只列出看起来能凑的组合。
独立重做后核对
答案依次为 0、-1、2、3、2。dp[0..10] 为 [0,-1,-1,1,-1,1,2,-1,2,3,2]（这里展示时用 -1 表示不可达；内部标记仍可使用 amount+1）。
- 关闭主问题答案并使用新输入独立完成。
- 给出结果与原因；失败时记录最小反例，不能只把完成标记改成通过。
重做的 30min 已计入本套4h；需要更多补课时记录实际用时，按缺口顺延。
记录实际回答与证据
# W07 算法 / 英文训练记录（仅个人练习，不是能力认证）
日期：
本次先备与尚不确定点：
主问题接口合同：
我最初的方案与状态表：
运行命令或设计事件编号：
失败输入 / 预期 / 实际：
修复与理由：
追问路径（节点 → 自己原话 → 缺口）：
英文第一轮两处含糊句：
英文第二轮修订：
次日重做日期（30 分钟已含本周预算）：
重做输入 / 实际结果 / 解释：
仍需补练：
本次练习的检查依据
反例、DP 表与独立实现相符；不可达不会参与有效转移；能指出直接并行各金额的依赖问题。
模板在你的个人笔记中填写。网页只提供空模板；不会把这次训练写成项目经验或学习验收结果。