问题描述

LeetCode 518. 零钱兑换 II (opens in a new tab)，难度中等。

给你一个整数数组 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

题解

在这个问题中，我们要找出用给定的硬币组合来凑成总金额的方法数量。首先我们找出状态转移方程。

我们设 dp[i] 表示凑成金额 i 的方法数量。现在，考虑我们有一系列的硬币面额，比如 coins = [c1, c2, ..., cn]。我们想要计算 dp[i]，也就是凑成金额 i 的方法数量。

为了构造金额 i，我们可以考虑最后一步加上的那枚硬币是什么。这枚硬币可以是任何一种硬币，比如 c1, c2, ..., cn。如果最后一步我们加上了面额为 c1 的硬币，那么在这一步之前，我们需要构造的金额就是 i - c1；同理，如果最后一步加上的是 c2，那么之前的金额就是 i - c2，以此类推。

因此，凑成金额 i 的方法数量 dp[i] 可以视为所有凑成金额 i - cj 的方法数量之和，其中 cj 是硬币的每一种面额。

dp[i] = dp[i - c1] + dp[i - c2] + ... + dp[i - cn]

为了实现这个方程，我们可以使用两层循环。外层循环遍历所有硬币面额，内层循环遍历从硬币面额到总金额的每一个值。每次内循环时，我们更新 dp[i] 的值。

为了避免数组越界，我们会检查 i - coin 是否非负，且只在这个条件满足时更新 dp[i]。因此，状态转移方程在代码中的实现形式为：

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

这样，dp[i] 会累加所有使用不同硬币组合凑成金额 i 的方法数，最终得到总的组合方式数量。

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < coins.length; ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}