硬币找零动态规划实现部分测试用例失败，寻求问题排查帮助

你遇到的硬币找零DP代码在部分测试用例失败的情况，我帮你梳理下常见的问题点，同时给你一个经过验证的实现，你可以对比着排查自己的代码。

常见错误点分析 #

• DP数组初始化错误：如果没把dp数组初始化为足够大的值（比如无穷大），仅将dp[0]设为0，后续的min计算会直接出错，导致得到错误的最少硬币数。
• 状态转移逻辑错误：遍历顺序搞反（比如先遍历硬币再遍历金额，虽然两种顺序都能解决最少硬币问题，但逻辑细节要注意），或者状态转移方程写错——比如没取最小值，或者计算dp[i-coin]+1时没判断i-coin是否合法（也就是i是否大于等于硬币面值）。
• 回溯过程错误：找到最少硬币数后，回溯找具体硬币时，没正确判断哪个硬币是组成当前金额的最优选择，导致输出的硬币列表不对，甚至遗漏正确组合。
• 未处理无法找零的情况：当目标金额没法用给定硬币组成时，没返回提示或空列表，直接让程序崩溃。

经过验证的动态规划实现 #

def coin_change(coins, amount):
    # 初始化dp数组，dp[i]代表组成金额i所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 金额0自然需要0个硬币
    
    # 状态转移：逐个遍历金额，再遍历每个硬币尝试更新最优解
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    
    # 若无法组成目标金额，返回空列表
    if dp[amount] == float('inf'):
        return []
    
    # 回溯推导具体的硬币组合
    result = []
    current = amount
    while current > 0:
        for coin in coins:
            # 找到能让当前金额最优解成立的硬币
            if current >= coin and dp[current] == dp[current - coin] + 1:
                result.append(coin)
                current -= coin
                break  # 找到一个就退出，继续处理剩余金额
    
    # 可选：给结果排序，让输出更规整
    result.sort()
    return result

# 测试示例
target = 63
coins = [1, 5, 10, 21, 25]
print(coin_change(coins, target))  # 输出 [21, 21, 21]

代码关键点说明 #

• DP数组初始化：用float('inf')标记初始状态下无法组成的金额，只有金额0的硬币数为0，这是动态规划的基础前提。
• 状态转移：对每个金额i，尝试用每一种硬币，如果使用该硬币后能得到更少的硬币数，就更新dp[i]的值。
• 回溯过程：从目标金额倒推，每次找到符合dp[current] = dp[current - coin] + 1的硬币（也就是组成当前金额的最优选择之一），加入结果列表后减去该硬币面值，直到金额归0。
• 异常处理：如果dp[amount]还是无穷大，说明目标金额无法被组成，直接返回空列表避免报错。

对比排查你的代码 #

你可以对照上面的实现，检查这几点：

1. 你的dp数组初始化是否正确？有没有把除dp[0]之外的元素都设为无穷大？
2. 状态转移时，是不是正确取了最小值，并且判断了i >= coin？
3. 回溯部分，是不是正确找到了符合条件的硬币？如果你的硬币是无序的，遍历顺序可能会导致选到不同的组合，但最少硬币数是对的——比如示例中的63，若回溯时先遍历25，可能会走弯路，这时候可以调整硬币的遍历顺序（比如把目标组合的硬币放在前面）。
4. 有没有处理无法找零的情况？比如当amount=3、coins=[2,5]时，应该返回空列表。

内容的提问来源于stack exchange，提问作者The Wanderer