苏小小移动网站,金寨县建设规划局网站,深圳泰安建设公司怎么样,wordpress 注册邮箱验证完全背包理论基础
视频链接#xff1a;带你学透完全背包问题#xff01; 和 01背包有什么差别#xff1f;遍历顺序上有什么讲究#xff1f;_哔哩哔哩_bilibili
完全背包与01背包不同的地方就是#xff1a;01背包每种物品只能取一次#xff0c;而完全背包每种物品可以取…完全背包理论基础
视频链接带你学透完全背包问题 和 01背包有什么差别遍历顺序上有什么讲究_哔哩哔哩_bilibili
完全背包与01背包不同的地方就是01背包每种物品只能取一次而完全背包每种物品可以取无数次。 leetcode 518.零钱兑换II
题目链接518. 零钱兑换 II - 力扣LeetCode
视频链接动态规划之完全背包装满背包有多少种方法组合与排列有讲究| LeetCode518.零钱兑换II_哔哩哔哩_bilibili 题目概述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1: 输入: amount 5, coins [1, 2, 5] 输出: 4
解释: 有四种方式可以凑成总金额: 55 5221 52111 511111
示例 2: 输入: amount 3, coins [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
示例 3: 输入: amount 10, coins [10] 输出: 1
思路
本题不强调元素顺序就像示例1中{221}与{122}是一种组合而不是两种所以本题求的是组合数不强调元素之间的顺序。本题是完全背包因为物品是可以取无限次的。
依旧是动规五部曲
1.确定dp数组以及下标含义
dp[j]凑成总金额j的货币组合数为dp[j]。
2.确定递推公式
dp[j] dp[j - coins[i]]求装满背包有几种方法公式都是dp[j] dp[j - nums[i]]本题公式是根据这个公式推理的来的。
3.dp数组初始化
dp[0] 1。
4.确定遍历顺序
虽然说完全背包中两层for循环是可以颠倒的但是本题就不行本题第一层for循环遍历钱物品第二层for循环遍历总额背包完全背包就不用特意强调内层循环必须要从后向前遍历。本题有顺序的原因就是因为我们要求的是组合数一旦颠倒顺序就变成求排列数了。
5.打印dp数组 代码实现
class Solution {
public:int change(int amount, vectorint coins) {vectorint 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];}
}; leetcode 377. 组合总和 Ⅳ
题目链接377. 组合总和 Ⅳ - 力扣LeetCode
视频链接动态规划之完全背包装满背包有几种方法求排列数| LeetCode377.组合总和IV_哔哩哔哩_bilibili 题目概述
给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。 示例 1
输入nums [1,2,3], target 4
输出7
解释
所有可能的组合为
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意顺序不同的序列被视作不同的组合。示例 2
输入nums [9], target 3
输出0 思路
本题其实和上一道题差不多唯一的区别就是本题是有序的要求排列数就是在遍历顺序上把两层for循环颠倒一下其余的几乎不变。
依旧是动规五部曲
1.确定dp数组以及下标含义
dp[i]: 凑成目标正整数为i的排列个数为dp[i]。
2.确定递推公式
dp[i] dp[i - nums[j]]。
3.dp数组初始化
dp[0] 1。
4.确定遍历顺序
第一层for循环遍历背包第二层for循环遍历物品。
5.打印dp数组 代码实现
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1,0);dp[0] 1;for(int i 0;i target;i) {for(int j 0;j nums.size();j) {if(i - nums[j] 0 dp[i] INT_MAX - dp[i - nums[j]]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
};
