应用题-动态规划-零钱兑换II( 完全背包-组合 )
- 版权声明：本站原创文章，于2026-05-19，由 管理员 发表。
- 转载请注明： 应用题-动态规划-零钱兑换II( 完全背包-组合 ) | CodeGarden
```python
class Solution:
# 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
# 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
def change(self, amount: int, coins: List[int]) -> int:
# 从物品coins中任意取多次, 装满amount, 物品的体积和价值相同, 问能够装满最大价值的种类数 —— 完全背包
# dp[ i ]: 容量为i的背包,装满的方式有dp[ i ]种
dp = [ 0 for _ in range( amount + 1 ) ]
dp[ 0 ] = 1
for v in coins:
for i in range( v, amount + 1 ):
dp[ i ] = dp[ i ] + dp[ i - v ]
return dp[ amount ]
```