第9章｜动态规划
Unit 05 · LeetCode #322 零钱兑换
不要保存“用了哪些硬币”，
只保存“这个金额最少要几枚”。
本单元从一个会欺骗贪心策略的微型金额开始。你会观察不同硬币序列如何抵达同一个剩余金额，再将整棵搜索树压缩为 dp[amount]。动画重点展示不可达状态、候选前驱和同一硬币的重复使用。
已恢复上次学习位置阶段、动画、答题、代码槽位和迁移进度均已恢复。
知识桥梁｜Unit 04 → Unit 05
Unit 04：固定位置的局部摘要
ending_here 保存一个可以被下一元素继续延长的连续区间摘要。
位置依赖 → 金额依赖
Unit 05：固定金额的最优摘要
dp[a] 保存凑出金额 a 的最少硬币数，未来金额只读取更小金额。
本单元贯穿问题当前金额的候选值来自哪个前驱金额？该前驱是真正可达，还是仍处于不可达状态？
LeetCode #322 原题题面转述、示例、约束与复杂度
题目要求
给定不同面额的整数数组 coins 和目标金额 amount，返回凑出该金额所需的最少硬币数量。每种硬币可以使用无限次；若无法凑出目标金额，返回 -1。
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
pass
约束
1 ≤ len(coins) ≤ 121 ≤ coins[i] ≤ 2³¹ - 10 ≤ amount ≤ 10⁴
示例
输入：coins = [1,2,5], amount = 11
输出：3
解释：11 = 5 + 5 + 1。
输出：3
解释：11 = 5 + 5 + 1。
输入：coins = [2], amount = 3
输出：-1。
输出：-1。
输入：coins = [1], amount = 0
输出：0。
输出：0。
主方法
一维动态规划。设 n = amount、硬币种类数为 m，时间复杂度 O(nm)，空间复杂度 O(n)。
金额状态
dp[a] 只回答“凑出 a 最少几枚”，不保存硬币顺序。
完全选择
同一面额可以反复使用，因此前驱状态仍可通过同一硬币继续转移。
不可达状态
inf 表示目前没有合法方案，不能与答案 0 混淆。
依赖顺序
当前金额只依赖更小金额，所以按金额递增计算。
六段认知流程
本环节已完成
请停留观察当前状态，确认你能够解释候选值的来源。