本文主要是介绍代码随想录算法训练营第四十四天| 完全背包，518. 零钱兑换 II ，377. 组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目与题解
完全背包
题目链接：完全背包
代码随想录题解：完全背包
视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？_哔哩哔哩_bilibili
解题思路：
看答案
看完代码随想录之后的想法
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历。
import java.util.*;public class ID52Kama {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int V = scanner.nextInt();int[] w = new int[N];int[] v = new int[N];for (int i = 0; i < N; i++) {w[i] = scanner.nextInt();v[i] = scanner.nextInt();}int[] dp = new int[V+1];for (int i = 0; i < N; i++) {for (int j = w[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - w[i]]+v[i]);}}System.out.println(dp[V]);}
}遇到的困难
不懂+1
518. 零钱兑换 II
题目链接：518. 零钱兑换 II
代码随想录题解：518. 零钱兑换 II
视频讲解：动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili
解题思路：
求有多少种方法的题，一维数组初始化dp[0]=1，递推公式为dp[j] += dp[j-coins[i]]即可，其余根完全背包一样，最后返回dp[amount]
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount+1];dp[0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
}看完代码随想录之后的想法
虽然看不懂，但是我很会照猫画虎。
遇到的困难
。。。
377. 组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
代码随想录题解：377. 组合总和 Ⅳ
视频讲解：动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV_哔哩哔哩_bilibili
解题思路：
虽然这道题叫组合总和，但其涉及到顺序不一样就是不一样的结果，本质上是排列问题。不会。
看完代码随想录之后的想法
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target+1];dp[0] = 1;for (int i = 0; i <= target; i++) { // 遍历背包for (int j = 0; j < nums.length; j++) { // 遍历物品if (i - nums[j] >= 0 && dp[i] < Integer.MAX_VALUE - dp[i - nums[j]]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
}遇到的困难
不懂
今日收获
继续懵逼
这篇关于代码随想录算法训练营第四十四天| 完全背包，518. 零钱兑换 II ，377. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
