322. 零钱兑换

leetcode 322. 零钱兑换

题目：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

提示:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

方法：动态规划

思路：因为硬币可以重复使用，因此这是一个完全背包问题。由于硬币面额为正整数，组成总金额amount的硬币数量不会超过amount个，在未知金币面额时，可以确定的是组成总金额0的最少硬币数为0，对于组成面额1~amount所需的最少硬币数是无法确定的，所以将组成金额的最小硬币数设置的尽可能大，初始为amount + 1，状态转移方程为：
$$
\begin{cases}
dp[j] = 0, & \text {j = 0} \\
dp[j] = min(dp[j], dp[j - coins[i]] + 1), & \text {j > 0}
\end{cases}
$$
j表示总金额，dp[j]表示组成总金额j所需的最少硬币数量，coins[i]表示提供的第i个硬币的面额。

运行数据：执行用时：16 ms，内存消耗：41 MB

复杂度分析：

• 时间复杂度：O(n * m)，n为不同面额的硬币数量， m为总金额。
• 空间复杂度：O(m)，m为总金额。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// LeetCode指定调用方法 
public int coinChange(int[] coins, int amount) {

    int maxValue = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, maxValue);
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
    }

    return dp[amount] == maxValue ? -1 : dp[amount];
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！