跳转至

LeetCode: 518. 零钱兑换 II

1、题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 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

注意:

你可以假设:

  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过 500 种
  • 结果符合 32 位符号整数

2、解题思路

  • 使用动态规划

  • dp[i]表示当前金额有多少种组合方式

  • 状态转换:

dp[i] += dp[i-coin]

coin表示硬币面额
  • 初始状态dp[0]=1

  • 对每一个面额,都从当前面额到目标面额进行更新

例如下面是示例1的中间过程:

[1, 1, 0, 0, 0, 0]
[1, 1, 1, 0, 0, 0]
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 1]
[1, 1, 2, 1, 1, 1]
[1, 1, 2, 2, 1, 1]
[1, 1, 2, 2, 3, 1]
[1, 1, 2, 2, 3, 3]
[1, 1, 2, 2, 3, 4]
4
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [1] + [0] * amount
        for c in coins:
            for i in range(c, amount + 1):
                dp[i] += dp[i - c]
        return dp[-1]