题目
零钱兑换 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
题解
解题分析
解题思路:
- 最长公共子序列问题是典型的二维动态规划问题。
- 题目复述:本题目中给定总金额为 amount, 和数组 coins, 要求计算金额只和等于 amount 的硬币组合数。其中,coins 中的美俄元素可以选取多次,不考虑元素的顺序,因此这个题目是需要计算硬币选取的组合数。
- 题目分析:我们可以通过动态规划的的方式来计算组数数。用 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] 的值。
- 思考和注意:对于上面的流程是否会存在重复计算的问题。不会, 因为外层循环的遍历的是 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]; }
提交后反馈结果(由于该题目没有进行优化,性能一般):