本题可以看出也是背包问题,但区别于之前的01背包问题,这个是完全背包问题的变形形式。
下面介绍01背包和完全背包的区别与联系:
- 01背包是背包中的物品只能用一次,不可以重复使用,而完全背包则是可以重复使用。
- 01/完全背包的递推公式(这里都是以一维数组的情况举例)是dp[j] = Math.max(dp[j],dp[j-weight[i]]+values[i])。
- 01背包的遍历顺序是先物品,再背包,并且背包遍历的时候是需要倒序遍历的,而完全背包则不需要,直接先物品再背包(背包需要正序),其实先背包再物品也可以,但为了方便记忆则和01保持一致。
而当在完全背包的变形形式,比如本题是要求组合数,组合是没有顺序的,只需要找出对应的元素就可以,所以递推公式是dp[j] += dp[j-nums[i]]。
所以本题中,我们可以想将背包中的硬币个数,不限制次数的选取,最后求凑成金额为amount的种类一共有多少种。
所以采用动态规划完全背包求组合情况
dp[j]表示背包容量为j的价值为dp[j]。
dp[j] += dp[j-nums[i]]
dp[0] = 1 (注意,这里必须是1,如果不是1的话没办法推出后面的数据,后面数据就都变成0了)。
遍历顺序应该先物品再背包,并且背包内层循环应该由小到大遍历。
打印
class Solution {
public int change(int amount, int[] coins) {
//递推表达式
int[] dp = new int[amount + 1];
//初始化dp数组,表示金额为0时只有一种情况,也就是什么都不装
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
注意:
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。