题目大意：
零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10] 输出: 1
注意:
你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=518
解题思路分析：
这是一道典型的动态规划题目，我们定义一个dp数组，dp[i]代表凑成总金额i的硬币组合数。初始dp[0]等于1，dp[amount]是最后的解。解题时，我们需要两层循环，第一层循环每种硬币，第二层，i从当前硬币的面值循环至amount，如果想计算dp[i]的值，我们需要知道 dp[i-coin] 的值，因为 i-coin 与 i 之间只相差了当前的coin，能够凑成 i-coin 的组合，再加上当前coin，就能组成i，因此: dp[i] += dp[i-coin] 。注意这里 dp[i] 是累加的，因为，对于每种coin（第一层循环）我们都能计算出一个dp[i]。
实现代码：
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1];
dp[0]=1;
for(int coin : coins){
for(int i=coin;i<=amount;i++){
dp[i]+=dp[i-coin];
}
}
return dp[amount];
}本解法执行时间为2ms。
Runtime: 2 ms, faster than 94.26% of Java online submissions for Coin Change 2.
Memory Usage: 37.2 MB, less than 30.23% of Java online submissions for Coin Change 2.
解法二：递归加记忆数组
之前的文章我们多次讲过，绝大多数的DP题目都可以使用递归加记忆数组的方式来解题，而本题就属于那一小部分无法使用递归来解题的部分。这里首先解释一下原因。理论上使用动态规划解题时，我们需要建立一个dp数组，数组的维数决定了我们需要循环的层数。而转为递归方式时，我们实际上是将循环过程变为了递归过程，另外dp数组变成了记忆数组，除此之外没有任何区别。而本题我们注意到，在使用dp解题时，我们使用到了滚动数组，dp[i]的值是不断累加的，实际上，dp数组原始的定义应该是二维，dp[i][j]代表使用j种硬币凑成总金额i的硬币组合数。 dp[amount][coins.length]是最终的答案。
对于这种降维操作，使用递归就难以实现（至少我还不会）。不过使用二维数组的情况下还是可以使用递归来解题的。本题的递归思想实际上很像dfs，我们可以将每个coin看做是一个节点，下一个节点可以是自己或者其他任何节点，dfs路线上的节点和若等于amount的话，说明我们找到了一种组合方式。dfs完所有路线，即可统计出所有组合方式。
实现代码：
Integer[][] memo; // 记忆数组
public int change(int amount, int[] coins) {
if(amount==0&&coins.length==0) return 1;
if(coins.length==0) return 0;
Arrays.sort(coins); // 排序树组
// 初始化记忆数组
memo=new Integer[amount+1][coins.length];
// 递归求解
return help(amount,coins,0);
}
// amt：需要凑成的总钱数
// coins：所有硬币
// index：可以使用的硬币范围[index, end]
int help(int amt, int[] coins, int index){
if(amt==0) return 1;
if(memo[amt][index]!=null) return memo[amt][index];
int res=0;
for(int i=index;i<coins.length;i++){
int coin=coins[i];
if(amt-coin>=0){
res+=help(amt-coin,coins,i);
}else break;
}
memo[amt][index]=res;
return res;
}本解法执行时间为25ms。
Runtime: 25 ms, faster than 8.71% of Java online submissions for Coin Change 2.
Memory Usage: 47.8 MB, less than 6.98% of Java online submissions for Coin Change 2.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-518-coin-change-2-解题思路分析/