零钱兑换：用最少的硬币凑出指定金额，怎么求？

直接回答：完全背包型 DP。设 dp[a] 为凑金额 a 所需的最少硬币数，初始 dp[0] = 0、其余为无穷大；转移 dp[a] = min(dp[a], dp[a − c] + 1) 对每个硬币面额 c 取最小。最终 dp[amount] 仍为无穷大则表示凑不出，返回 −1。时间 O(amount × 硬币种数)、空间 O(amount)。

展开解析：每种硬币可以无限使用，所以是完全背包——内层金额循环正序（与 0-1 背包的逆序相对，逆序保证每种物品只用一次）。两个易混变体务必区分：「最少硬币数」求 min，初始化无穷大；「凑出金额的硬币组合数」求和，初始化 dp[0]=1 且硬币循环必须在外层（否则会把不同顺序算成不同方案）。复杂度陷阱也要提：DP 复杂度是伪多项式（依赖 amount 的数值而非位数），金额极大而硬币种类少时存在更优的数论做法但不实用。追问方向：如何回溯输出具体硬币组合（记录决策前驱）、BFS 解法（按金额分层扩展）为什么也正确。

示例：

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        dp[a] = min((dp[a - c] for c in coins if a >= c), default=INF) + 1
    return dp[amount] if dp[amount] <= amount else -1