深圳高端网站建设招聘,360网站收录提交,网站建设建议,箱包东莞网站建设目录 动态规划#xff1a;完全背包理论基础Leetcode518.零钱兑换IILeetcode377. 组合总和 Ⅳ 动态规划#xff1a;完全背包理论基础 文章链接#xff1a;代码随想录 题目链接#xff1a;卡码网#xff1a;52. 携带研究材料 思路#xff1a;完全背包问题#xff0c;物品可… 目录 动态规划完全背包理论基础Leetcode518.零钱兑换IILeetcode377. 组合总和 Ⅳ 动态规划完全背包理论基础 文章链接代码随想录 题目链接卡码网52. 携带研究材料 思路完全背包问题物品可以无限取即不用考虑是否重复添加在一维滚动数组解法上将背包遍历变为正序。
# include bits/stdc.h
using namespace std;void solve(int N, int V){vectorint dp(V 1);vectorint weight(N), value(N);for (int i 0; i N; i){cin weight[i] value[i];}for (int i 0; i N; i){for (int j weight[i]; j V; j){dp[j] max(dp[j], dp[j - weight[i]] value[i]);}}cout dp[V] endl;
}int main(){int N ,V;cin N V;solve(N , V);return 0;
}Leetcode518.零钱兑换II 文章链接代码随想录 题目链接518.零钱兑换II 思路完全背包求组合问题改一下状态转移方程即可。
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1);dp[0] 1;for (int i 0; i coins.size(); i){for (int j coins[i]; j amount; j){dp[j] dp[j - coins[i]];}}return dp[amount];}
};Leetcode377. 组合总和 Ⅳ 文章链接代码随想录 题目链接377. 组合总和 Ⅳ 思路完全背包求排列问题先遍历背包再遍历物品注意用例超界。
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1);dp[0] 1; for (int j 0; j target; j){for (int i 0; i nums.size(); i){if (j nums[i] dp[j] INT_MAX - dp[j - nums[i]]) dp[j] dp[j - nums[i]];}}return dp[target];}
};第四十四天打卡加油
