Leetcode 322 零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3
输出:-1

示例 3:

输入:coins = [1], amount = 0
输出:0

示例 4:

输入:coins = [1], amount = 1
输出:1

示例 5:

输入:coins = [1], amount = 2
输出:2

解题思路

这道题有些人可能会想到贪心法,优先用面值大的硬币去凑,但是贪心无法获得最优解。例如下面这个例子:

int[] coins = {1, 2, 5, 7, 10};
int amount = 14;

假如用贪心法,那么首先肯定是用面值为 10 的硬币,然后还需两个面值为 2 的硬币,总共需要 3 个硬币。但事实上,只需要两个面值为 7 的硬币就能凑出 14 的金额。因此这道题需要用动态规划的思想。

从下面这个表格可以看出动态规划的思路,对于需要拼凑的金额 i,遍历硬币面值,找到面值比金额低的硬币 coins[j] ,然后再去看 dp 数组中 dp[i - coins[j]] 是否有最优解,把所有可能的情况都列出,找最小的即可。整个过程从 1 开始不断迭代,一直迭代到需要的金额即可。

金额 可以凑出的情况 最优解
0 - 0
1 1 1(使用一个面值为 1 的硬币)
2 2 1(使用一个面值为 2 的硬币)
3 1 + dp[2], 2 + dp[1] 2(都是最优解)
4 1 + dp[3], 2 + dp[2] 2(2 + dp[2])
5 5 1(使用一个面值为 5 的硬币)
6 1 + dp[5], 2 + dp[4], 5 + dp[1] 2(1 + dp[5] 或者 5 + dp[1])
7 7 1(使用一个面值为 7 的硬币)
8 1 + dp[7], 2 + dp[6], 5 + dp[3], 7 + dp[1] 2(1 + dp[7] 或者 7 + dp[1])
9 1 + dp[8], 2 + dp[7], 5 + dp[4], 7 + dp[2] 2(2 + dp[7] 或者 7 + dp[2])
10 10 1(使用一个面值为 10 的硬币)
11 1 + dp[10], 2 + dp[9], 5 + dp[6], 7 + dp[4], 10 + dp[1] 2(1 + dp[10] 或者 10 + dp[1])
12 1 + dp[11], 2 + dp[10], 5 + dp[7], 7 + dp[5], 10 + dp[2] 2(2 + dp[10] 或者 5 + dp[7] 或者 7 + dp[5] 或者 10 + dp[2])
13 1 + dp[12], 2 + dp[11], 5 + dp[8], 7 + dp[6], 10 + dp[3] 3(都是最优解)
14 1 + dp[13], 2 + dp[12], 5 + dp[9], 7 + dp[7], 10 + dp[4] 2(7 + dp[7])

参考代码

import java.util.Arrays;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; // 初始化 dp 数组,大小为 amount + 1
        Arrays.fill(dp, -1); // 全部元素初始化为 -1
        dp[0] = 0; // 金额 0 的最优解 dp[0]=0

        // 依次计算 1 至 amount 的最优解
        for (int i = 1; i <= amount; i++) {
            // 对于每个金额 i ,遍历面值 coins 数组
            for (int j = 0; j < coins.length; j++) {
                // 需要拼凑的面额 i 比当前面值 coins[j] 大,且金额 i - coins[j] 有最优解
                if (coins[j] <= i && dp[i - coins[j]] != -1) {
                    // 如果当前金额还未计算或者 dp[i] 比当前计算的值大
                    if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1) {
                        dp[i] = dp[i - coins[j]] + 1; // 更新 dp[i]
                    }
                }
            }
        }
        return dp[amount]; // 返回金额 amount 的最优解 dp[amount]
    }
}

你可能感兴趣的