佛山做网站,网站建设实训 考核要求,网络服务协议需要交印花税吗,wordpress保存图片时加水印这部分的题目主要介绍了完全背包的内容#xff1b;
主要考虑了两种情况#xff0c;求组合数还是排列数
先遍历背包#xff0c;再遍历物品#xff0c;得到的就是组合数#xff0c;也就是有顺序
for (int j 0; j amount; j) { // 遍历背包容量for (int i 0; i
主要考虑了两种情况求组合数还是排列数
先遍历背包再遍历物品得到的就是组合数也就是有顺序
for (int j 0; j amount; j) { // 遍历背包容量for (int i 0; i coins.size(); i) { // 遍历物品if (j - coins[i] 0) dp[j] dp[j - coins[i]];}
}
先遍历物品再遍历背包得到的就是有顺序的物品会从序号从小到大出现
for (int i 0; i coins.size(); i) { // 遍历物品for (int j coins[i]; j amount; j) { // 遍历背包容量dp[j] dp[j - coins[i]];}
}
纯背包问题不需要考虑顺序。
另外还有一个点求最小值dp数组初始化都要为遍历过程中取不到的大值一般为INT_MAX
518零钱兑换
class Solution {
public:int change(int amount, vectorint coins) {vectorintdp(amount1,0);dp[0]1;for(int i0;i coins.size();i){for(int jcoins[i];jamount;j) { dp[j]dp[j-coins[i]];coutdp[j]endl;}}return dp[amount];}
};
//组合数 不需要考虑顺序 所以先遍历物品
377组合数IV
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorunsigned intdp(target1,0);dp[0]1;for(int j1;jtarget;j){for(int i0;i nums.size();i){if(jnums[i])dp[j]dp[j]dp[j-nums[i]];}}return dp[target];}
};
70爬楼梯
class Solution {
public:int climbStairs(int n) {vectorint dp(n 1, 0);dp[0] 1;for (int i 1; i n; i) { // 遍历背包for (int j 1; j m; j) { // 遍历物品if (i - j 0) dp[i] dp[i - j];}}return dp[n];}
};
322零钱兑换
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorintdp(amount1,amount2);dp[0]0;for(int i1;idp.size();i){for(int coin:coins){if(i-coin0)dp[i]min(dp[i],dp[i-coin]1);}}return dp[amount]amount2?-1:dp[amount];}
};
279完全平方数
class Solution {
public:int numSquares(int n) {vectorintdp(n1,n2);dp[0]0;dp[1]1;for(int i2;in;i){for(int j1;j*ji;j){dp[i]min(dp[i],dp[i-j*j]1);}}return dp[n];}
};
139单词拆分
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbooldp(s.size()1);dp[0]true;for(int i1;is.size();i){for (int j 0; j i; j){string word s.substr(j, i - j);if (wordSet.find(word) ! wordSet.end() dp[j]) {dp[i] true;}}}return dp[s.size()];}
};
