0518. 零钱兑换 II #

• 标签：数组、动态规划
• 难度：中等

题目大意 #

给定一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

要求：计算并返回可以凑成总金额的硬币组合数。如果无法凑出总金额，则返回0。

假定：每一种面额的硬币枚数为无限个。

解题思路 #

完全背包问题。「 322. 零钱兑换」中计算的是凑成总金额的最少硬币个数，而这道题计算的是凑成总金额的硬币组合数。

可以转换为有 n 枚不同的硬币，每种硬币可以无限次使用。凑成总金额为 amount 的背包，总共有多少种组合方式。

动态规划的状态 dp[i] 可以表示为：凑成总金额为 i 的组合数。

动态规划的状态转移方程为：dp[i] = dp[i] + dp[i - coin]，意思为凑成总金额为 i 的组合数 = 「不使用当前 coin，只使用之前硬币凑成金额 i 的组合数」+「使用当前 coin 凑成金额 i - coin 的方案数」。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:

        dp = [0 for _ in range(amount + 1)]
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]

        return dp[amount]