本文主要是介绍代码随想录训练营Day 46|力扣完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.完全背包
视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？_哔哩哔哩_bilibili
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html
代码：（动态规划）
#include <bits/stdc++.h>
using namespace std;
void test_completePack(vector<int>& weight, vector<int>& value, int V,int N){// dp数组的定义及初始化vector<int> dp(V + 1,0);// 完全背包j要正序遍历，保证物品不会只被添加一次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 ;vector<int> weight;vector<int> value;for(int i = 0; i < N; i++){int w;int v;cin >> w >> v;weight.push_back(w);value.push_back(v);}test_completePack(weight,value,V,N);return 0;
}思路：
01背包的滚动数组需要倒叙遍历，保证每个物品只被添加一次。而且，因为要求的dp值依赖于上一行的状态，只能先遍历物品，再遍历背包。
完全背包的滚动数组需要正序遍历，保证每个物品可以被添加多次。而且，因为要求的dp值只依赖同一行的之前求出来的dp值，先遍历物品还是背包都可以。
dp数组的含义：在物品可选种类为0~i的前提下，尽量装满容量为j的背包所获得的最大价值为dp[j]
dp数组的递推公式：和之前的一样dp[j] = max(dp[j],dp[j - weight[i]] + value[i])
dp数组的遍历顺序：正序遍历，先背包还是先遍历物品无所谓
dp数组初始化：为了不影响后序求最大值，全部初始化为0
2.零钱兑换2
视频讲解：动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili
代码随想录
代码： （动态规划）
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1,0);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];}
};思路：
dp数组的含义：用coins里的下标为0~i的元素装满容量为j的背包的方法数为dp[j]
dp数组的递推公式： 和昨天做的目标和的递推公式一样，思路也一样
dp数组的遍历顺序：正序遍历，必须先遍历物品（因为求的是组合数）如果是先遍历背包，物品次序不同也会被算作不同的方法，这是在求排列数，不符合要求。
dp数组的初始化：dp[0] = 1 dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递推结果将都是0。
3.组合总和 4
视频讲解：动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV_哔哩哔哩_bilibili
代码随想录
代码：（动态规划）
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1,0);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];}
};思路：
dp数组的含义：用nums里的下标为0~i的元素装满容量为j的背包的方法数为dp[j]
dp数组的递推公式： 和昨天做的目标和的递推公式一样，思路也一样
dp数组的遍历顺序：正序遍历，必须先遍历背包，因为物品次序不同也会被算作不同的方法，我们在求排列数
dp数组的初始化：dp[0] = 1 dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递推结果将都是0。
细节：为了使得递推公式不会越界访问元素，要加上判断条件 j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]
这篇关于代码随想录训练营Day 46|力扣完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
