第9章｜动态规划
Unit 07 · LeetCode #518 零钱兑换 II
转移式没有变，
循环顺序却改变了“你在数什么”。
本单元不把“硬币在外、金额在内”当口诀。你会亲眼看到：以硬币种类为阶段时，每个组合只会在最后开放其最大硬币时出现一次；以金额为阶段时，不同选择顺序会被分别计数。
已恢复上次学习位置阶段、动画、答题、代码和迁移进度均已恢复。
知识桥梁｜Unit 06 → Unit 07
Unit 06：每个位置最多一次
倒序容量保护旧层，使当前数组位置不会在同一轮被再次读取。
0/1 选择 → 完全选择＋计数语义
Unit 07：每种硬币可无限次
金额正序允许当前硬币反复使用；外层阶段决定是否区分硬币出现顺序。
本单元贯穿问题当前新增方案是按“使用了哪些硬币”分类，还是按“最后一步选择了哪个硬币”分类？
LeetCode #518 原题题面转述、示例、约束与函数签名
题目要求
给定不同面额的硬币数组 coins 和总金额 amount，返回可以凑成该金额的硬币组合数量。每种硬币可以使用任意多次；如果无法凑成，返回 0。组合不考虑硬币选择顺序。
from typing import List
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
pass
约束
1 ≤ coins.length ≤ 3001 ≤ coins[i] ≤ 5000，且面额互不相同0 ≤ amount ≤ 5000- 答案保证在 32 位有符号整数范围内
示例
输入：amount = 5, coins = [1,2,5]
输出：4
组合：5；2+2+1；2+1+1+1；1+1+1+1+1
输出：4
组合：5；2+2+1；2+1+1+1；1+1+1+1+1
输入：amount = 3, coins = [2]
输出：0
输出：0
输入：amount = 10, coins = [10]
输出：1
输出：1
目标复杂度
时间复杂度 O(len(coins) × amount)；空间复杂度 O(amount)。
六段主流程
本环节已完成
页面不会自动跳转。请停留观察当前循环游标、来源状态和新增方案，再主动进入下一阶段。