共计 1639 个字符，预计需要花费 5 分钟才能阅读完成。
给你一个整数数组 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]
}
}
正文完
