美元找零组合计数Python代码逐行逻辑及range用法咨询

这段代码为动态规划实现的1美元（100美分）硬币找零组合数计算程序，可用硬币面值包括1美分、5美分、10美分、25美分、100美分。以下是对应问题的解答：

1 range函数的具体作用与运行规则 #

range()是Python内置的整数序列生成函数，常用调用规则如下：

• 单参数调用range(n)：生成从0开始、到n-1结束的连续整数，默认步长为1
• 双参数调用range(a, b)：生成从a开始、到b-1结束的连续整数，默认步长为1
• 三参数调用range(a, b, step)：生成从a开始，每次累加step，直到数值小于b的整数序列

本段代码中用到的range(type_of_coin, change_needed+1)属于双参数调用：

• 因为要计算的金额最小是当前硬币面值（小于该面值的金额无法使用当前硬币），最大是目标金额100美分
• 所以上限设置为change_needed+1，才能把100纳入生成的序列范围

2 核心循环段的逐行含义及算法逻辑 #

该算法属于完全背包类动态规划，核心是统计不考虑硬币顺序的凑钱组合总数，逐行解释如下：

初始化行 #

combinations = [1]+[0]*change_needed

• 数组combinations的下标代表要凑的金额，对应下标存储的数值为凑该金额的总组合数
• 初始的[1]对应凑0美分的情况：仅有一种方案（不用任何硬币）
• 后续的100个0为初始占位值，代表凑1~100美分的组合数初始为0，后续逐步更新

第一层循环 #

for type_of_coin in coins_used:

• 遍历所有可用的硬币面值，本轮依次遍历1、5、10、25、100美分
• 每轮循环的作用是：计算新增当前面值硬币后，各个金额的组合数更新值

第二层循环 #

for m in range(type_of_coin, change_needed+1):

• 遍历从当前硬币面值到目标金额100的所有金额m，小于当前硬币面值的金额无法使用该硬币，无需计算

组合数更新行 #

combinations[m] += combinations[m-type_of_coin]

• 逻辑原理：凑m金额的总组合数 = 原本不用当前面值硬币的组合数 + 使用至少1枚当前面值硬币的组合数
• 使用至少1枚当前硬币的组合数等价于combinations[m-type_of_coin]：只要凑出m - 当前硬币面值的金额，再加1枚当前硬币就能得到m金额的组合

可以用小例子辅助理解：计算凑5美分的组合数

1. 遍历1美分硬币的循环结束后，combinations[5]的值为1，对应方案：5枚1美分
2. 遍历5美分硬币的循环时，m=5触发更新，combinations[5] += combinations[0]，得到新值2，对应新增方案：1枚5美分，符合实际组合数

完整可运行代码 #

change_needed = 100
coins_used = [1, 5, 10, 25, 100,]

combinations = [1]+[0]*change_needed

for type_of_coin in coins_used:
    for m in range(type_of_coin, change_needed+1):
        combinations[m] += combinations[m-type_of_coin]

print('Total Number of Combinations:', combinations[change_needed])

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