LC322. 零钱兑换

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

题目解析

题目在说什么

这道题是让你用一些硬币（比如1元、2元、5元）来凑出一个指定的总金额（比如11元），并且要求用的硬币数量最少。你可以认为每种硬币的数量是无限的，也就是说你可以随便用多少个1元、2元、5元。如果无论如何都凑不出这个总金额，就返回-1。

比如，给你硬币面额 [1, 2, 5] 和总金额 11，你可以用两个5元和一个1元凑出11元，一共用了3个硬币，这就是最少的数量。所以答案是3。

思路是怎么来的

想象一下，你在超市买东西，需要付11元，但你只有一堆1元、2元、5元的硬币。你肯定想尽量用大面额的硬币，因为这样用的数量少。但有时候大面额不一定能正好凑出总金额，比如如果只有5元和2元，要凑出11元，你可能会先考虑用两个5元（10元），还差1元，但你没有1元硬币，所以不行。这时候你可能就得调整，比如用一个5元和三个2元（5+2+2+2=11），用了4个硬币。所以这个问题其实是在所有可能的组合中，找到硬币数量最少的那一种。

怎么系统地找到这个最少数量呢？一个很自然的想法是：从0元开始，一点点往上加。比如，先想凑1元最少需要几个硬币，再想凑2元最少需要几个，一直到凑11元。而且，凑某个金额的时候，我们可以利用已经算出来的更小金额的结果。比如，要凑11元，我们可以先想：如果最后一步用的是5元硬币，那么之前需要凑6元（11-5=6），而凑6元的最少硬币数我们之前已经算过了，那么凑11元就可能是“凑6元的最少硬币数 + 1（这个5元硬币）”。同样，如果最后一步用的是2元，那么之前需要凑9元；如果最后一步用的是1元，那么之前需要凑10元。我们只需要比较这三种情况，选最小的那个就行。

这种“从小的金额开始，逐步推导到大的金额”的方法，就是动态规划。而因为每种硬币可以用无限次，所以这是一个“完全背包”问题——你可以反复拿同一种硬币。

代码逐步拆解

我们来看参考代码，它用了一个二维数组来记录结果。我们一步步拆开看。

1. 定义状态

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

这里 dp[i][j] 表示：使用前 i 种硬币（也就是硬币列表里的前 i 种，比如 coins[0]、coins[1]……直到 coins[i-1]）来凑出金额 j 所需要的最少硬币数。注意，i 从0到n，j 从0到amount。

为什么是 n+1 和 amount+1？因为我们要考虑“用了0种硬币”和“凑0元”的情况，所以多出一行和一列。

2. 初始化

for( int i = 0 ; i <= n ; i++){
    for( int j = 0 ; j <= amount ;j++){
        dp[i][j] = amount + 1;
    }
}
dp[0][0] = 0;

一开始，我们把所有 dp[i][j] 都设成一个很大的数（amount + 1），这表示“目前还没找到可行的方案”。因为最多可能用 amount 个1元硬币（如果全是1元），所以 amount + 1 是一个比任何可能答案都大的数，用来表示“不可能”。然后，我们设置 dp[0][0] = 0，意思是：用0种硬币凑0元，需要0个硬币，这是唯一一个已知的可行方案。

3. 双重循环

for( int i = 1 ; i <= n ; i++){
    for( int j = 0 ; j <= amount; j++){

外层循环 i 从1到n，表示我们依次考虑每一种硬币。内层循环 j 从0到amount，表示我们依次考虑每一个金额。

4. 状态转移

if( j < coins[i-1]){
    dp[i][j] = dp[i-1][j];
} else {
    dp[i][j] = Math.min(dp[i-1][j], dp[i][j - coins[i-1]] + 1);
}

这里分两种情况：

• 情况1：当前金额 `j` 小于第 `i` 种硬币的面额 `coins[i-1]`

比如，当前硬币是5元，但你想凑的金额是3元，那这个5元硬币根本用不上。所以，凑3元的最少硬币数，就和不用这个5元硬币时一样，也就是 dp[i-1][j]（只用前 i-1 种硬币的结果）。

• 情况2：当前金额 `j` 大于等于硬币面额

这时，我们可以选择“用”或“不用”这个硬币。

• 如果不用，结果就是 dp[i-1][j]（只用前 i-1 种硬币）。