Cocolib零钱兑换II
TIP
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合32位带符号整数。
思路
动规五部曲
- 确定dp数组以及下标的含义：
dp[i]：amount =i时的硬币组合数。 - 确定递推公式：
dp[j]=dp[j-coins[i]]+dp[j] - dp数组如何初始化：
dp[0] = 0、dp[非0] = 1 - 确定遍历顺序
- 举例推导dp数组
js
var change = function(amount, coins) {
let dp = Array(amount + 1).fill(0)
dp[0] = 1
for(let i=0;i<coins.length;i++){
for(let j=coins[i];j<=amount;j++){
dp[j] += dp[j-coins[i]]
}
}
return dp[amount]
};组合不强调元素之间的顺序，排列强调元素之间的顺序。
- 先物品后背包：组合
- 先背包后物品：排列