官方链接
https://leetcode-cn.com/problems/coin-change/
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1示例 2:
输入: coins = [2], amount = 3
输出: -1说明: 你可以认为每种硬币的数量是无限的。
思路
状态树 的边表示用了哪个硬币，第 n 层表示已经用了几个硬币, 在状态树中找值为 0, 且深度最小的节点
- 暴力递归: 指数 O(2^n)
- BFS: 遍历状态树, 最早发现数字为零的节点时, 遍历的层数，就是我们要找的最少硬币数
- DP
a. subproblems b. dp array f(n) = min{f(n-k), for k in [1,2,5])} + 1 c. DP 方程
如果问有多少种不同的组合，则和爬楼梯一样了 另外，看看官方题解，比如说递归的写法
解法一
动态规划
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin: coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// return dp[amount] > amount ? -1: dp[amount];
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
// 这里如果用 Integer.MAX_VALUE, 后面 +1 会溢出, 而 amount+1 为超过 amount 的第一个数字，刚好拿来当最大值用
Arrays.fill(dp, amount+1);
dp[0] = 0;
for(int coin: coins) {
for(int i = coin; i < amount + 1; i++) {
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
if (dp[amount] != amount+1) return dp[amount];
else return -1;
}
}