建设网站的目的和功能定位,天水 网站建设,苏州工业园区属于哪个区,公众号wordpress思路#xff1a;和第一道是一样的问题#xff0c;也就是完全背包问题。
我们首先可以看到#xff0c;每一个数都是可以重复使用的#xff0c;而且#xff0c;数的选择上有两种#xff0c;一种就是选#xff0c;一种就是不选。所以会想到完全背包问题。
上一个题的零钱…思路和第一道是一样的问题也就是完全背包问题。
我们首先可以看到每一个数都是可以重复使用的而且数的选择上有两种一种就是选一种就是不选。所以会想到完全背包问题。
上一个题的零钱兑换是对于完全背包容量恰好装满的变形形式需要对于f数组进行初始化然后转移状态这里呢只是对于方案数输出的变形所以我们只需要让除f[0]之外的数组初始值为0就可以了。f[0]1因为这代表我们容量为0的时候的方案数就只有全部都不选这一种方案。
上代码
class Solution {
public:int change(int amount, vectorint coins) {vectorintf(5005,0);int ncoins.size();f[0]1;for(int i0;in;i){for(int j0;jamount;j){if(jcoins[i])f[j]f[j];elsef[j]f[j]f[j-coins[i]];}}return f[amount];}
};
