零钱兑换 [dfs -＞ 背包]

前言

零钱兑换是一个很经典的问题，可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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

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

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

参考文献

[1] LeetCode 零钱兑换