算法训练营第四十四天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

动态规划：完全背包理论基础

文章链接：代码随想录
题目链接：卡码网：52. 携带研究材料

思路：完全背包问题，物品可以无限取，即不用考虑是否重复添加，在一维（滚动）数组解法上，将背包遍历变为正序。

# include <bits/stdc++.h>
using namespace std;void solve(int N, int V){vector<int> dp(V + 1);vector<int> 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, vector<int>& coins) {vector<int> 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(vector<int>& nums, int target) {vector<int> 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];}
};

第四十四天打卡，加油！！！