考察点:完全背包(硬币可无限用)的最值模型,以及『初始化无穷大』的细节与遍历方向。
思路:这是『完全背包』求最小值的经典题——每种硬币可用无限次,目标凑出 amount 且硬币数最少。
要点(状态与转移):
dp[j] = 凑出金额 j 的最少硬币数;初始化 dp[0]=0,其余 inf(表示不可达)。dp[j] = min(dp[j], dp[j - coin] + 1),对每个 coin 遍历 j 从 coin 到 amount(顺序遍历即可,因为硬币可重复用)。def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for c in coins:
for j in range(c, amount + 1):
dp[j] = min(dp[j], dp[j - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
要点(注意):
dp[0]=0、其余 inf 是关键,否则 min 会被 0 污染;最终不可达返回 -1。题目与答案就在本页;收藏、批注和错题重练在应用内