Leetcode 518. 零钱兑换 II(DP YYDS)

àì夳堔傛蜴生んèń 2022-09-12 01:54 171阅读 0赞

## 题目重述 ##

给你一个整数数组 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/coin-change-2  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

*  如果不选取硬币，这种组合方法算是一种
 *  使用dp一位数组来保存组合的总数，`dp[i]`代表组合金额`i`情况下的方法数
 *  对硬币数组进行遍历，对于每个硬币，都可以累加dp数组,即 `dp[j] += dp[j-coin];`

## Java实现 ##

// 冲刺092 刷题小队
    // https://leetcode-cn.com/problems/coin-change-2/
    class Solution {
        
        public int change(int amount, int[] coins) {
        
            int[] dp = new int[amount+1];
            // base case
            // 不选取硬币，这种组合方法算是一种
            dp[0]=1;
            for(int i=0;i<coins.length;i++){
        
                int coin = coins[i];
                for(int j=coin;j<=amount;j++){
        
                    // 注意这里是加号，因为是对组合办法的综合
                    dp[j] += dp[j-coin];
                }
            }
            return dp[amount];
        }
    }