如何将递归实现的硬币找零计数函数改写为for迭代的动态规划版本

你原来的递归逻辑本质是完全背包问题的「选/不选当前面额」状态转移，我们直接用一维动态规划数组实现迭代版，完全规避重复子问题，运行效率远高于递归，且没有使用贪心算法，结果准确率和原递归完全一致。

实现代码 #

coins = [50,40,20,10,5,4,2,1]  
m = 80

def coin_count(coins, m):
    if m == 0:
        return 0
    # 初始化dp数组，dp[i]表示凑出金额i的最少硬币数，初始值设为比最大可能值大的数
    max_val = m + 1
    dp = [max_val] * (m + 1)
    dp[0] = 0
    # 逐个处理每个面额，对应原递归里的coins[0]选择逻辑
    for coin in coins:
        # 面额比目标金额大的直接跳过，对应原递归里的coins切片跳过逻辑
        if coin > m:
            continue
        # 遍历所有大于等于当前面额的金额，更新最优解
        for j in range(coin, m + 1):
            # dp[j]对应原递归的n1：不使用当前面额的最优解
            # dp[j - coin] + 1对应原递归的n2：使用至少1张当前面额的最优解
            dp[j] = min(dp[j], dp[j - coin] + 1)
    # 因为面额包含1，必然有解，直接返回dp[m]即可
    return dp[m]

# 测试
print(coin_count(coins, m)) # 输出为2，对应两张40面额，结果正确

逻辑对齐说明 #

• 外层遍历每个硬币面额的逻辑，完全对应原递归中每次处理coins[0]的流程
• 状态转移的min计算和原递归min(n1, n2)的逻辑完全一致
• 自动跳过大于当前金额的面额，和原递归的coins = coins[1:]跳过逻辑一致
• 时间复杂度为O(coins长度 * m)，空间复杂度为O(m)，远优于递归实现的指数级时间复杂度

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