322. 零钱兑换

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

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

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

322. 零钱兑换

示例 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<=121 <= coins.length <= 121<=coins.length<=12
• 1<=coins[i]<=231−11 <= coins[i] <= 2^{31} - 11<=coins[i]<=231−1
• 0<=amount<=1040 <= amount <= 10^40<=amount<=104

思路：(动态规划)

此问题属于 0-1背包 的 完全背包 ，解法和 0-1背包类似：
0 - 1背包问题（万能统一代码）

定义一个二维数组dp 存储所需硬币个数，其中 dp[i][j] 表示前 i 个硬币 可以凑成总金额 为 j 所需最少的硬币个数：

• 每种硬币的数量是无限的，所以可以重复使用
• 状态转移方程为：
  dp[i][j]=min(dp[i−1][j],dp[i][j−coins[i]]+1)dp[i][j] = min(dp[i - 1][j], dp[i ][j - coins[i]] + 1)dp[i][j]=min(dp[i−1][j],dp[i][j−coins[i]]+1)

观察前 i 个硬币的状态仅与前 i-1 个硬币的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]：状态转移方程为：
dp[j]=min(dp[j],dp[j−coins[i]]+1)dp[j] = min(dp[j], dp[j - coins[i]] + 1)dp[j]=min(dp[j],dp[j−coins[i]]+1)

代码：(Java)

import java.util.Arrays;public class CoinChange {public static void main(String[] args) {// TODO Auto-generated method stubint[] coins = {1, 2, 5};int amount = 11;System.out.println(coinChange(coins, amount));}public static int coinChange(int[] coins, int amount) {if(amount == 0) {return 0;}int[] dp = new int[amount + 1];for(int i = 0; i < coins.length; i++) {if(coins[i] > amount) {continue;}dp[coins[i]] = 1;for(int j = coins[i] + 1; j <= amount; j++) {if(dp[j - coins[i]] != 0 && (dp[j] == 0 || dp[j] > dp[j - coins[i]] + 1)) {dp[j] = dp[j - coins[i]] + 1;}}}return dp[amount] == -1 ? 0 : dp[amount];}
}

运行结果：

复杂度分析：

• 时间复杂度：O(len∗amount)O(len * amount)O(len∗amount), lenlenlen 为数组 coinscoinscoins 的长度，amountamountamount 为要凑成的总金额。
• 空间复杂度：O(amount)O(amount)O(amount) ，需要开辟一个一维数组 dp ， 长度为amount+1amount + 1amount+1 ，amountamountamount 为要凑成的总金额。

注：仅供学习参考！

题目来源：力扣。