题目定位
这题非常适合 DP，因为每个金额都依赖更小的金额，而转移又要求你完整考虑所有硬币选择。
关键观察
对于金额 a，最优解就是某个可达金额 a - coin 的最优解再加一。
目标复杂度
O(amount * coins) / O(amount)
这题的解法思路怎么拆
1
这题非常适合 DP，因为每个金额都依赖更小的金额，而转移又要求你完整考虑所有硬币选择。
2
对于金额 a，最优解就是某个可达金额 a - coin 的最优解再加一。
3
先用自然语言命名状态。
4
列出哪些决策会转移到这个状态。
参考实现
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
常见坑点
warning
对任意硬币面值误用贪心选最大。
warning
不可达状态初始化不严谨。
高频追问
它和“统计组合数”的背包题有什么不同？
如果每个硬币只能用一次，怎么改？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。