518 零钱兑换 II（完全背包问题）

系统管理员 2022-08-30 04:12 252阅读 0赞

**1. 问题描述：**

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。

**示例 1：**

输入：amount = 5，coins = \[1，2， 5\]  
输出：4

解释：有四种方式可以凑成总金额：

5=5  
5=2+2+1  
5=2+1+1+1  
5=1+1+1+1+1

**示例 2：**

输入：amount = 3，coins = \[2\]  
输出：0  
解释：只用面额 2 的硬币不能凑成总金额 3 。

**示例 3：**

输入：amount = 10, coins = \[10\]  
输出：1

**提示：**

1 <= coins.length <= 300  
1 <= coins\[i\] <= 5000  
coins 中的所有值互不相同  
0 <= amount <= 5000  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/coin-change-2

**2. 思路分析：**

分析题目可以知道这是一道**选择性**的问题（题目中涉及到"凑"的字眼），对于选择性的组合问题我们可以想到背包问题，每一个硬币都有无限个所以属于经典的**完全背包问题**。我们可以将硬币看成是物品，总金额amount看成是背包的容量，硬币的面额看成是物品的体积，我们需要求解在背包容量为amount的前提下恰好装满背包的方案数目，可以使用一维数组或者一维列表来解决这个问题，完全背包问题的一维状态转移方程为：dp\[j\] += dp\[j - v\]，其中j为当前背包的容量，v为当前物品的体积；

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def change(self, amount: int, coins: List[int]) -> int:
             n = len(coins)
             dp = [0] * (amount + 1)
             # 初始状态, 当背包容量为0的时候属于一种合法的方案
             dp[0] = 1
             for i in range(n):
                  v = coins[i]
                  # 按顺序枚举体积即可
                  for j in range(v, amount + 1):
                       dp[j] += dp[j - v]
             return dp[amount]