零钱兑换

1. 题目描述

给你一个整数数组coins表示不同面额的硬币，另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回0。假设每一种面额的硬币有无限个，题目根据保证结果符合32位带符号整数。

样例输入 #1

输入：amount = 5, coins = [1, 2, 5]

样例输出 #1

输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

2. 分析

假设我们有以下输入： coins = [1, 2, 5] amount = 11 我们需要计算使用面额为1、2和5的硬币，可以组合成总金额11的不同方式的数量。 步骤如下：

1. 初始化一个数组dp，长度为amount + 1，所有元素初始值为0。dp[i]表示凑成金额i的组合数。
2. 设置dp[0] = 1，因为凑成金额0有一种方法，即不使用任何硬币。
3. 遍历每一种硬币面额，对于每种面额coin，从coin开始到amount，更新dp数组：
   • dp[j] += dp[j - coin]，其中j是当前金额，coin是当前硬币面额。
   • 这个公式的含义是：要凑成金额j，可以选择不使用当前硬币（即dp[j]的值不变），或者使用至少一枚当前硬币（即增加dp[j - coin]的值）。
4. 最终，dp[amount]就是答案，即凑成总金额amount的组合数。

3. 代码

 int[][] memo;
    public int change(int amount, int[] coins){
        int len = coins.length;
        memo = new int[len][amount+1];
        for(int i=0;i<len;i++){
            Arrays.fill(memo[i],-1);
        }
        return reverse(coins,0,amount);
    }

    public int reverse(int[] coins,int start,int amount){
        if(start==coins.length || amount<0){
            return 0;
        }
        if(amount==0){
            return 1;   //返回组合方式
        }

        if(memo[start][amount]!=-1){
            return memo[start][amount];
        }

        int res = 0;
        for(int i = start;i<coins.length;i++){
            amount = amount - coins[i];
            res += reverse(coins,i,amount);
            amount = amount + coins[i];
        }
        memo[start][amount]=res;
        return memo[start][amount];
    }