一、题目描述

​ 在美国，硬币按照面值1，5，10，25，50来铸造(单位为美分)。现在考虑按照面值{d₁,…, d_k}(单位为分)来铸造硬币的某个国家.我们想统计有多少种方式能找开n分钱，并记种数为C(n)。例如当所在国家硬币面值集合为{1,6,10}时,C(5)=1,C(6)到C(9)都是2，C(10)=3，C(12)=4。

​ 给出一种高效算法来算出C(n)并分析该算法的时间/空间复杂度。(提示:通过计算C(n,d)来解决问题,C(n,d)是最高面值为d情况下能找开n分钱的方式种数.千万注意不要重复计数.)

​ ———题目来源：《算法设计指南》

示例：

输入：coins = [2,3,5] total = 10
输出：4
解释：2 + 3 + 5是一种
	 2 + 2 + 3 + 3是一种
	 2 + 2 + 2 + 2 + 2 + 2是一种
     5 + 5是一种
     总共4种。

• 1
• 2
• 3
• 4
• 5
• 6
• 7

二、解题思路（最朴素方法）

1. 定义状态

​ 设dp[i][j]表示使用前i个面值不同的硬币找出零钱j的方案数。

2. 定义状态转移方程

$$dp[i][j]=\sum _{k=0}^n(dp[i-1][j-k\times d_i])$$ ，其中$$n=\lfloor \frac{j}{d_i}\rfloor$$ 。这里解释一下$dp[i-1]$表示使用前$i-1$个面值不同的硬币，其中第$i$个硬币可能使用0个或多个，上限为$\lfloor \frac{j}{d_i}\rfloor$ 个，下限为0个。

3. 初始化

​ dp[0][j]表示不使用硬币找出j的方案数，根据实际情况是找不出来的，故初始化为0。

​ dp[i][0]表示使用前i个面值不同硬币找出0美分的方案数量，很显然dp[i][0]初始化为1即可。

三、代码实现

/**
 * 第8章第7题 找零钱问题
 *
 * @author hh
 */
public class Solution {

    /**
     *找零钱的方案数
     *
     * @param coins 硬币面值集合
     * @param total 找的零钱总数
     * @return 方案数
     */
    public int exchange(int[] coins,int total) {
        int[][] dp = new int[coins.length + 1][total + 1];
        //dp[0][i] = 0,i > 0时
        for(int i = 1; i <= total; i++){
            dp[0][i] = 0;
        }
        for(int i = 0; i <= coins.length ; i++){
            dp[i][0] = 1;
        }
        for(int i = 1; i <= coins.length ; i++){
            for(int j = 1; j <= total ; j++){
                dp[i][j] = 0;
                for(int k = 0; k <= (j / coins[i -1]) ; k++){
                    dp[i][j] += dp[i-1][j - k * coins[i - 1]];
                }
            }
        }
        return dp[coins.length ][total];
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        int[] coins = new int[]{2,3,5};
        int total = 10;
        System.out.println(solution.exchange(coins,total));
    }

}

• 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

四、优化

对于解题思路中的k其实是没必要计算的，这样就减少了一个循环。状态方程变为：

​ $$dp[i][j]=sum(dp[i-1][j],dp[i][j-d_i])$$

表示的含义是前i-1种硬币凑成j的方案数加上前i种硬币凑成j - d_i的方案数。第二个式子表示最少有一枚硬币i凑成零钱总数j的方案数。

代码如下所示：

public class Solution2 {

    /**
     * 找零钱的方案数
     *
     * @param coins 硬币面值集合
     * @param total 找的零钱总数
     * @return 方案数
     */
    public int exchange(int[] coins, int total) {
        int[][] dp = new int[coins.length + 1][total + 1];
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 0; j <= total; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= coins[i - 1]) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        return dp[coins.length][total];
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int[] coins = new int[]{2, 3, 5};
        int total = 10;
        System.out.println(solution.exchange(coins, total));
    }

}

• 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

上面是对时间复杂度进行优化，下面对空间进行优化，考虑到dp[i][j]只跟dp[i-1]和dp[i]有关，我们可以把二维降成一维，代码如下所示：

public class Solution3 {

    /**
     * 找零钱的方案数
     *
     * @param coins 硬币面值集合
     * @param total 找的零钱总数
     * @return 方案数
     */
    public int exchange(int[] coins, int total) {
        int[] dp = new int[total + 1];
        dp[0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = coins[i - 1]; j <= total; j++) {
                dp[j] += dp[j - coins[i - 1]];
            }
        }
        return dp[total];
    }

    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        int[] coins = new int[]{2, 3, 5};
        int total = 10;
        System.out.println(solution.exchange(coins, total));
    }

}

• 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

五、执行结果