LC518. 零钱兑换II

题目描述

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

题目解析

题目在说什么

想象你是一个收银员，手上有几种面额的硬币（比如1元、2元、5元），每种硬币都有无限多个。现在顾客给了你一个总金额（比如5元），你需要找出所有可能的组合方式，用这些硬币凑出这个金额。注意，组合和顺序无关，比如“1元+2元+2元”和“2元+1元+2元”算同一种方式。

题目给了三个例子：

• 金额5元，硬币有1、2、5元，有4种组合（5元本身、2+2+1、2+1+1+1、1+1+1+1+1）。
• 金额3元，只有2元硬币，凑不出来，返回0。
• 金额10元，只有10元硬币，只有1种组合。

你只需要输出组合的数量，不需要列出具体组合。

思路是怎么来的

这个问题很像一个经典的“背包问题”。想象你有一个背包（总金额），你要往里面塞东西（硬币），每种东西（硬币）可以无限次使用。但这里不是问“能不能塞满”，而是问“有多少种不同的塞法”。

关键点：因为硬币无限，而且顺序不重要，所以我们需要一种方法，保证每种组合只被计算一次。比如，先考虑用1元硬币，再考虑用2元硬币，这样就不会重复计算“1+2”和“2+1”。

怎么想到用动态规划？ 动态规划是一种“记住过去结果”的方法。比如，要凑出5元，可以先想：如果我已经知道怎么凑出4元、3元……，那么凑5元就简单了。比如，我可以用1元硬币加上凑4元的方法，或者用2元硬币加上凑3元的方法，等等。但这样会重复，所以我们需要一种“按顺序”的思考方式。

核心思想： 我们按硬币的种类一个一个来考虑。先只用第一种硬币，看能凑出哪些金额；然后加入第二种硬币，看能增加哪些新组合；以此类推。这样，每种组合只会被计算一次，因为组合中的硬币顺序是固定的（比如先1元后2元）。

怎么用数学表达？ 定义一个表格 dp[i][j]，表示“用前 i 种硬币（即硬币列表的前 i 个）凑出金额 j 有多少种方法”。

• 初始状态：dp[0][0] = 1，表示用0种硬币凑0元，有1种方法（什么都不用）。
• 对于每种硬币，我们有两种选择：不用它，或者用它（可以多次用）。
• 不用它：方法数等于用前 i-1 种硬币凑出 j 的方法数，即 dp[i-1][j]。
• 用它：方法数等于用前 i 种硬币（包括它自己）凑出 j - 硬币面额 的方法数，即 dp[i][j - coin]。因为用了它之后，剩下的金额还可以继续用这种硬币。
• 所以总方法数 = 不用它 + 用它，即 dp[i][j] = dp[i-1][j] + dp[i][j - coin]。

为什么是“完全背包”？ 因为每种硬币可以无限使用，这就是“完全背包”问题的特点。在代码中，我们通过内层循环从小到大遍历金额，来保证每种硬币可以多次使用。

代码逐步拆解

我们先用二维数组的版本讲解，因为它更容易理解。然后看一维优化版本。

二维数组版本

int[][] dp = new int[coins.length + 1][amount + 1];
dp[0][0] = 1;

• dp[i][j] 的行 i 表示“使用了前 i 种硬币”，列 j 表示“凑出金额 j”。
• 初始化 dp[0][0] = 1：用0种硬币凑0元，只有1种方法（什么都不做）。其他 dp[0][j] 默认是0，因为不用任何硬币凑不出正数金额。

for (int i = 1; i <= coins.length; i++) {
    for (int j = 0; j <= amount; j++) {
        if (j < coins[i-1]) {
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]];
        }
    }
}

• 外层循环 i 从1到硬币种类数，表示依次考虑每种硬币。注意：coins[i-1] 是当前硬币的面额，因为数组下标从0开始。
• 内层循环 j 从0到总金额，表示考虑所有可能的金额。
• 如果当前金额 `j` 小于当前硬币面额：说明这个硬币太大，用不了，所以只能继承之前的方法数：dp[i][j] = dp[i-1][j]。