给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

 

示例 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

 

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000
Related Topics
  • 数组
  • 动态规划

  • 👍 617
  • 👎 0

    • 以需要凑出0到amount金额来处理，已有零钱面值为[1,2,5]，
    热知识：现有的货币面值单位就是[1,2,5],这是一个非常高效的组合，具体更多原因和背后考量可以自行深入研究下

    已知0元的情况，直接不用任何面值可以记为1种情况。

    • 当我们有了面值为1的硬币之后，
      • 如果一定要用面值为1的硬币的话，显然凑不出0元，只能使用原来只有0元的时候的情况
      • 而如果面值大于0了，可以用当前面值减去面值为1的情况加一个硬币得来
    • 当我们有了面值为2的硬币之后，
      • 如果想要凑出面值小于2的情况，显然是不行的，只能用之前的方案代替
      • 而大于等于2的时候，可以选择 前面的当前面值减去2元的情况加上一枚2元的硬币来组成 或者 之前没有2元面值的时候凑出2元的方案
    • 到这里逻辑和转化方程就都已经清楚了f [i][j] = f [i − 1][j] + f [i][j − x]
    • 最后拿总额11来再说明下
      • 可以是之前没有5元面值的时候凑出11元的方案
      • 也可以是需要有5元面值硬币的时候凑出6元的方案加一个5元硬币.

    代码

    我们把越界索引为负数的部分当做0处理

    class Solution {
    public int change(int amount, int[] coins) {
        int [][] dp = new int[coins.length+1][amount+1];
        dp[0][0] = 1;
        for (int row = 1; row <= coins.length; row++) {
            for (int col = 0; col <= amount; col++) {
                dp[row][col] = dp[row-1][col] + (col>=coins[row-1]?dp[row][col-coins[row-1]]:0);
            }
        }
        return dp[coins.length][amount];
    }
}

    再思考下

    每多出来一种面值硬币的可选项之后，都是在之前已得到方案的结果上进行叠加处理，那么可以只声明一个长度为amount+1的数组，在每多加一种面值硬币的时候就对结果进行重新叠加统计处理。而小于新加的硬币的面值的总额不必处理，和前面说到的情况一样。
    大概如图，可能有点不是太清晰，中间省略了几步

    1. 预定义了dp[0] = 1
    2. 从面值为1的硬币开始遍历处理，当面值0的情况加1枚1元硬币，可以得到总额1，后面挨个加可以得到[1,1,1,1,1,1,1,1,1,1,1,1]的结果
    3. 新加入了面值2，在原来的基础上，面值为0的情况加1枚硬币2可以得到总额为2的情况1种，累加上原来面值为2的情况1种，此时可以有2中情况可以凑出面值2，后面依次遍历处理
    4. 中间省略
    5. 最后新加了面值5，依旧从面值0开始加一个5元面值硬币则代表一种新的凑出5元的方案，加上原来的方案数量3种，此时可知有4种方法凑出5元
    6. 最后的11元等于之前的6种情况加上使用5元凑出6元的6种方案，一共11种方案
    class Solution {
    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];
    }
}