本文主要是介绍leetcode 518.零钱兑换 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路:和第一道是一样的问题,也就是完全背包问题。
我们首先可以看到,每一个数都是可以重复使用的,而且,数的选择上有两种,一种就是选,一种就是不选。所以会想到完全背包问题。
上一个题的零钱兑换是对于完全背包容量恰好装满的变形形式,需要对于f数组进行初始化,然后转移状态;这里呢只是对于方案数输出的变形,所以我们只需要让除f[0]之外的数组初始值为0就可以了。f[0]=1,因为这代表我们容量为0的时候的方案数,就只有全部都不选这一种方案。
上代码:
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int>f(5005,0);int n=coins.size();f[0]=1;for(int i=0;i<n;i++){for(int j=0;j<=amount;j++){if(j<coins[i])f[j]=f[j];elsef[j]=f[j]+f[j-coins[i]];}}return f[amount];}
};
这篇关于leetcode 518.零钱兑换 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!