LeetCode 518 零钱兑换II
给你一个整数数组 coins
表示不同面额的硬币,另给一个整数 amount
表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0
。
假设每一种面额的硬币有无限个。
题目数据保证结果符合32位带符号整数。
示例:
输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
动态规划
本题是一个经典的完全背包的变体,此时背包的容量就是 amount
,物品的重量为 coins
,求解物品将背包装满的方案数。不同于之前0/1背包问题的变体(494.目标和),此处的硬币数量是无限的,并且是完全对于硬币做加法的。
那么这样的完全背包问题就适用于动态规划求解:
动态规划数组的定义:定义数组
dp[amount+1]
表示在背包容量为amount
时,将背包装满的方案数动态规划数组的推导:在第
i
次迭代中,考虑元素coins[i]
,可以选取 0/n 个元素coins[i]
,那么递推公式为dp[j]=dp[j]+dp[j-coins[i]]
动态规划数组的初始化:在初识时在元素
coins[0]
中选取元素尝试装满背包,那么对于元素coins[0]
的倍数容量的背包就都能够被装满,也就是存在一种可行的方案。for(int i=0;i*coins[0]<=amount;i++) dp[i*coins[0]]=1;
动态规划数组的遍历顺序:此处采取先遍历硬币再遍历背包的方式,遍历的顺序都是从前向后遍历。
举例验证:对于
coins={1,2,5},amount=5
动态规划数组的变化为:验证正确
dp={1,1,1,1,1,1}
dp={1,1,2,2,3,3}
dp={1,1,2,2,3,4}
代码实现:
1 | class Solution { |
对换遍历顺序:先遍历背包,再遍历物品,也就是初始的背包容量为0,那么 dp[0]=1
。逐步增加背包的容量,每一次计算的是,背包容量为 j
时,将背包装满的最大方案数。采取: dp[j]=j>=coins[i]?dp[j]+dp[j-coins[i]]:dp[j];
的方式去递推,这样的递推方式存在一个问题,将单纯的选择问题转换为了有序的,这样的计算方式:在当前尝试选择元素 coins[i]
,例如对于 dp[3]
机会出现: dp[3]=dp[1]+dp[2]
此处将方案:1,2 和 2,1
进行了重复计算。因此在本题中遍历的顺序需要是先遍历物品在遍历背包。
关于遍历的顺序:
- 如果求组合数就是外层for循环遍历物品,内层for遍历背包。
- 如果求排列数就是外层for遍历背包,内层for循环遍历物品。