动态规划：得到目标货币的方法数（有限张货币 + 面值相同的货币相同）

1、题目

arr 是货币数组，其中的值都是正数。

再给定一个正数 aim。

每个值都认为是一张货币，认为值相同的货币没有任何不同，返回组成 aim 的方法数。

例如：arr = {1,2,1,1,2,1,2}，aim = 4

方法：1+1+1+1、1+1+2、2+2，一共就3种方法，所以返回3。

2、思路

依然是 从左向右尝试模型。

准备两个数组：货币面值数组 与 每种面值的货币张数数组

• 暴力递归版本

public class CoinsWaySameValueSamePaper {
    public static class Info {
        public int[] coins; //面值数组
        public int[] zhangs; //张数
        
        public info(int[] c, int[] z) {
            coins = c;
            zhangs = z;
        }
    }
    
    public static Info getInfo(int[] arr) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        //遍历数组记录每种面值的词频，遍历结束counts中记录了每种面值的张数
        for (int value : arr) {
            if (!counts.containsKey(value)) {
                counts.put(value, 1);
            } else {
                counts.put(value, counts.get(value) + 1);
            }
        }
        
        int n = counts.size(); //面值种类数
        int[] coins = new int[n];
        int[] zhangs = new int[n];
        int index = 0;
        for (Entry<Integer, Integer> entry : counts.entrySet()) {
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }
        return new Info(coins, zhangs);
    }
    
    public static int coinsWay(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        return process(info.coins, info.zhangs, 0, aim);
    }
    
    //coins 面值数组，正数且去重
    //zhangs 每种面值对应的张数
    //coins: [2， 5， 10]
    //zhangs: [4， 6， 3]
    //index : 0   1  2
    //index... index及其后面的所有面值在张数规定好的情况下组成rest的方法数
    public static int process(int[] coins, int[] zhangs, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0；
        //当前index号面值的张数从0开始尝试，但是 使用的张数的总面值不能超过总钱数 && 张数不能超过规定好的
        for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs； zhang++) {
            ways += process(coins, zhangs, index + 1, rest - (zhang * coins[index]));
        }
        return ways;
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

• 动态规划版本

public class CoinsWaySameValueSamePaper {
    public static class Info {
        public int[] coins; //面值数组
        public int[] zhangs; //张数
        
        public info(int[] c, int[] z) {
            coins = c;
            zhangs = z;
        }
    }
    
    public static Info getInfo(int[] arr) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        //遍历数组记录每种面值的词频，遍历结束counts中记录了每种面值的张数
        for (int value : arr) {
            if (!counts.containsKey(value)) {
                counts.put(value, 1);
            } else {
                counts.put(value, counts.get(value) + 1);
            }
        }
        
        int n = counts.size(); //面值种类数
        int[] coins = new int[n];
        int[] zhangs = new int[n];
        int index = 0;
        for (Entry<Integer, Integer> entry : counts.entrySet()) {
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }
        return new Info(coins, zhangs);
    }
    
    public static int coinsWay(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        int n = coins.length;
        int[][] dp = new int[n + 1][aim + 1];
        dp[n][0] = 1;
        for (int index = n - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
                    ways += dp[index + 1][rest - (zhang * coins[index])];
                }
                dp[index][rest] = ways;
            } 
        }
        
        return dp[0][aim];
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

观察：与 动态规划：得到目标货币的方法数（无限张货币） 题目不同的是， 下图中的✔️位置只依赖于 a、b、c，而☆位置依赖于 b、c、d：

如果还按照 动态规划：得到目标货币的方法数（无限张货币） 的思路——✔️ = ☆ + a，那么就多了个 d ，所以需要减去 d ，即 ✔️ = ☆ + a - d。

抽象化：

特殊情况：比如给定的货币数组中 3元 有 100 万张（永远用不完），aim = 14，那么 ☆ 依赖的位置逻辑上是比✔️依赖的位置多，但是那已经是越界的位置，这个时候就不用再减。

• 动态规划优化版本

public class CoinsWaySameValueSamePaper {
    public static class Info {
        public int[] coins; //面值数组
        public int[] zhangs; //张数
        
        public info(int[] c, int[] z) {
            coins = c;
            zhangs = z;
        }
    }
    
    public static Info getInfo(int[] arr) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        //遍历数组记录每种面值的词频，遍历结束counts中记录了每种面值的张数
        for (int value : arr) {
            if (!counts.containsKey(value)) {
                counts.put(value, 1);
            } else {
                counts.put(value, counts.get(value) + 1);
            }
        }
        
        int n = counts.size(); //面值种类数
        int[] coins = new int[n];
        int[] zhangs = new int[n];
        int index = 0;
        for (Entry<Integer, Integer> entry : counts.entrySet()) {
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }
        return new Info(coins, zhangs);
    }
    
    public static int coinsWay(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        int n = coins.length;
        int[][] dp = new int[n + 1][aim + 1];
        dp[n][0] = 1;
        for (int index = n - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];//上图中的a位置
                if (rest - coins[index] >= 0) { //如果减完之后不越界
                    dp[index][rest] += dp[index][rest - coins[index]]; //获得✔️左边的☆号
                }
                if (rest - coins[index] * (zhangs[index] + 1) >= 0) {//检查是否多加了：rest - (极限张数 + 1) * 面值 如果还大于0，那就是多加了
                    dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[index] + 1)]; //减去多加的部分
                }
            } 
        }
        
        return dp[0][aim];
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

这就是通过观察邻近位置优化枚举行为，枚举行为就是为求每一个格子的时候出现了for循环。

有枚举行为的时候推严格位置依赖进行观察，尝试用邻近位置优化掉枚举行为；如果没有枚举行为，那么傻缓存（记忆化搜索）这一步其实就是最优解了。