前言

零钱兑换是一个很经典的问题，可dfs进行暴力寻找，结合一些剪枝，一般来说很容易超时。所以必须空间时间中和，采用记忆化数组记录中间节点到叶子节点过程的状态，防止重复计算；也可直接采用动规来进行递推求解。

一、零钱兑换

二、dfs & 背包

1、dfs+剪枝暴力搜索

// 零钱兑换
public class CoinChange {// dfs倒序寻找，找到第一个和为amount的就是最小coins数。// bug:可能中间的组合，其元素个数还要小一些。// 虽然硬币不多，但是可以重复选择，时间复杂度就根amount的大小有关了，直接超时。// 用数组把重复计算的位置的状态记录下来。public int coinChange(int[] coins, int amount) {if (amount < 1) return 0;Arrays.sort(coins);//降低栈深度。return dfs(coins, amount, new int[amount]);}private int dfs(int[] coins, int amount, int[] count) {// 递归正常结束。if (0 >= amount) return 0 == amount ? 0 : -1;// 记忆搜索。if (count[amount - 1] != 0) return count[amount - 1];int min = Integer.MAX_VALUE;// 不能以cur的方式，每一遍应该面向整个coins，才能记住正确的count[amount]!for (int i = coins.length - 1; i >= 0; i--) {int r = dfs(coins, amount - coins[i], count);if (r != -1 && r < min) min = r + 1;}count[amount - 1] = min == Integer.MAX_VALUE ? -1 : min;return count[amount - 1];}
}

2、空间换时间–背包

// dfs由于amount和coins的value原因，导致超时，所以空间换时间，采用一维背包解决。
class CoinChange2 {// f[amount]:组成amount的最小硬币数。public int coinChange(int[] coins, int amount) {int[] f = new int[amount + 1];// 和到amount即可。// 状态转移。for (int i = 1; i <= amount; i++) {// 小心-1的情况。f[i] = i < coins[0] ? -1 : f[i - coins[0]];if (f[i] != -1) f[i]++;for (int k = 1; k < coins.length; k++) {// 背包里不能为负。if (i >= coins[k]) {if (f[i] != -1 && f[i - coins[k]] != -1) f[i] = Math.min(f[i], f[i - coins[k]] + 1);else if (f[i - coins[k]] != -1) f[i] = f[i - coins[k]] + 1;}}}return f[amount];}}

总结

1）dfs超时问题，要么降低栈深度+多维剪枝；要么记忆数组；要么动规解决。

2）零钱兑换是一个面向整个零钱数组，递归开辟n层for循环问题。除此之外，也是一个经典的背包问题。

参考文献

[1] LeetCode 零钱兑换