题目

零钱兑换 II

给你一个整数数组 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. 最长公共子序列问题是典型的二维动态规划问题。

2. 题目复述：本题目中给定总金额为 amount， 和数组 coins， 要求计算金额只和等于 amount 的硬币组合数。其中，coins 中的美俄元素可以选取多次，不考虑元素的顺序，因此这个题目是需要计算硬币选取的组合数。

3. 题目分析：我们可以通过动态规划的的方式来计算组数数。用 dp[x] 来表示金额只喝等于 x 的组合数，然后求出 dp[amount] .

• 动态规划的边界值 dp[0] = 1. 只有当不选择任何硬币的时候，金额之和才为 0 ， 因此只有 1种 硬币组合。

• 对于面额为 coin 的硬币，只有当 coin <= i <= annont 的时候，如果存在一种硬币组合的金额只和等于 i - coin , 则在该硬币组合中增加一个面额的硬币 coin 的硬币，即可以得到一种金额只和等于 i 的硬币组合。因此需要遍历 coins 对于每一种面额的硬币。，更新数组 dp 中每个大雨或者等于该面额的元素的值。

• 总结动态规划的流程

 1). 初始化 dp[0]  =1;

 2). 遍历 coins, 对于其中的每个元素 coin， 进行如下操作： - 遍历 i 从 coin 到 amount , 将 dp[i-coin] 的值累加到 dp[i]

 3). 最终得到 dp[amount] 的值。

5. 思考和注意：对于上面的流程是否会存在重复计算的问题。不会， 因为外层循环的遍历的是 coins 的值，内层循环是遍历 不同的金额只和，在计算 dp[i] 的值时，可以确保金额只和 i 的涮许，由于顺序确定，因此不会存在重复的排列。

复杂度:

时间复杂度： O(M*N)

空间复杂度： O(M)

解题代码

题解代码如下（代码中有详细的注释说明）：

int change(int amount, int* coins, int coinsSize){
        // 数组
        int dp[amount +1];
        // 数组初始化
        memset(dp, 0, sizeof(dp));
        // 初始化第一个值
        dp[0] = 1;
        // 所有的零钱
        for (int i = 0; i < coinsSize; i++) {
               // 零钱组合
               for (int j = coins[i]; j <= amount; j++) { 
                   dp[j] += dp[j - coins[i]];
               }
        }
        return dp[amount];
}

提交后反馈结果（由于该题目没有进行优化，性能一般）：

参考信息

• 力扣 518. 零钱兑换 II

• 动态规划