代码随想录算法训练营 Day32 | 动态规划 part05

52. 携带研究材料第七期模拟笔试题目描述小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的重量并且具有不同的价值。小明的行李箱所能承担的总重量是有限的问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。输入描述第一行包含两个整数nv分别表示研究材料的种类和行李所能承担的总重量接下来包含 n 行每行两个整数 wi 和 vi代表第 i 种研究材料的重量和价值输出描述输出一个整数表示最大价值。输入示例4 51 22 43 44 5输出示例10#include iostream #include vector using namespace std; int main(){ int n, bagSize; cin n bagSize; vectorint w(n 1); vectorint v(n 1); // 读入物品的重量和价值您的代码从下标 0 开始读入完全没问题 for(int i 0; i n; i) cin w[i] v[i]; // 1. 定义 DP 数组 // dp[j] 表示容量为 j 的背包能装下的最大价值 vectorint dp(bagSize 1, 0); // 2. 遍历物品 for(int i 0; i n; i){ // 3. 遍历背包容量 —— 核心变化正序遍历 for(int j 0; j bagSize; j){ if(j w[i]){ // 递推公式与 0-1 背包一模一样 // 区别全在遍历顺序上 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } } cout dp[bagSize]; return 0; }总结1. 为什么正序遍历就能实现“无限次使用”以计算dp[5]且当前物品重量w[i] 2为例0-1 背包逆序计算dp[5]时需要用dp[3]。因为逆序dp[3]还没被更新它代表没有放当前物品时的状态。所以当前物品只能放 1 次。完全背包正序计算dp[5]时需要用dp[3]。因为正序dp[3]已经被更新过了。此时的dp[3]已经包含了当前物品所以dp[5] dp[3] v[i]相当于在dp[3]的基础上又放了一次当前物品。这样就实现了物品的重复选取。2. 优化在完全背包中我们可以直接把j的起始点设为w[i]省略掉if判断代码会更简洁for(int i 0; i n; i){ // 直接从 w[i] 开始正序遍历 for(int j w[i]; j bagSize; j){ dp[j] max(dp[j], dp[j - w[i]] v[i]); } }3. 纯背包问题的总结对照表特性0-1 背包完全背包物品数量只能选 1 次可以选无数次一维数组遍历顺序逆序 (j bagSize - w[i])正序 (j w[i] - bagSize)递推公式dp[j] max(dp[j], dp[j-w] v)dp[j] max(dp[j], dp[j-w] v)518. 零钱兑换 II给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回0。假设每一种面额的硬币有无限个。题目数据保证结果符合 32 位带符号整数。class Solution { public: int change(int amount, vectorint coins) { int n coins.size(); // 1. 定义 DP 数组 // dp[j] 表示凑成总金额 j 的硬币组合数 // 【高光细节】这里必须用 uint64_t 或者 long long // 因为组合数会非常大普通的 int 会在 LeetCode 的测试用例中溢出导致错误 vectoruint64_t dp(amount 1, 0); // 2. 初始化 // 凑成金额 0 的组合数是 1即“什么都不选”这一种方法 dp[0] 1; // 3. 状态转移 // 外层遍历物品硬币面额 for(int i 0; i n; i){ // 内层遍历背包容量目标金额 // 完全背包正序遍历从当前硬币面额开始 for(int j coins[i]; j amount; j){ // 递推公式求组合数累加方案数 // dp[j] 不用当前硬币的组合数 使用当前硬币的组合数 dp[j] dp[j - coins[i]]; } } return (int)dp[amount]; } };总结1. 为什么外层必须是物品内层是背包这是求 组合数 和求 排列数 的核心区别。外层物品内层背包 - 求组合数假设coins [1, 5]。当外层循环固定是1时内层循环会把所有包含1的组合算出来如[1,1,1]。当外层循环走到5时它只能加在之前算出的结果后面如[1,1,1,5]。结果5永远在1的后面。算出来的是 组合[1,5] 和 [5,1] 算同一种。外层背包内层物品 - 求排列数假设coins [1, 5]目标金额是 6。当外层循环走到金额6时内层循环先遇到1算出[...1]接着遇到5算出[...5]。如果在某次循环中先凑出了 5下一次金额 6 循环时先遇到 1就会变成[5, 1]。结果1和5的顺序可以颠倒。算出来的是 排列。2.uint64_t的妙用在 C 中int最大只能表示约 21 亿。对于稍微大一点的amount组合数会呈指数级增长。使用uint64_t(无符号 64 位整数) 完美避开了溢出报错最后强转回int返回。3. 复杂度分析时间复杂度O(N×M)N 是硬币种类数M 是目标金额。空间复杂度O(M)。377. 组合总和 Ⅳ给你一个由 不同 整数组成的数组nums和一个目标整数target。请你从nums中找出并返回总和为target的元素排列的个数。题目数据保证答案符合 32 位整数范围。class Solution { public: int combinationSum4(vectorint nums, int target) { int n nums.size(); // 1. 定义 DP 数组 // dp[j] 表示凑成目标和为 j 的排列总数 // 依然使用 uint64_t 防止极端用例下的整型溢出 vectoruint64_t dp(target 1, 0); // 2. 初始化 // 凑成目标和为 0 的排列数是 1什么都不选 dp[0] 1; // 3. 状态转移 // 【核心考点】外层遍历背包目标内层遍历物品数字 for(int j 0; j target; j){ for(int i 0; i n; i){ // 防止数组越界 if(j nums[i]){ // 递推公式与求组合数完全一样累加方案数 dp[j] dp[j - nums[i]]; } } } return dp[target]; } };总结1. 题目解析为什么叫“组合”却求“排列”LeetCode 这道题的名字极具误导性。题目描述中说“不同的序列被视为不同的组合”。在正常的数学定义中[1, 3]和[3, 1]是同一种组合但属于两种不同的排列。题目既然把不同顺序算作不同结果那么它本质上求的就是 排列数。2. 遍历顺序外层j内层i代码求排列外层是target。当我们要计算dp[6]时我们会依次把nums里的数放进去试。如果nums [1, 2, 3]计算dp[6]时先加dp[5]意味着排列的最后一步是 1再加dp[4]意味着排列的最后一步是 2再加dp[3]意味着排列的最后一步是 3效果1可以在前面也可以在后面元素的先后顺序被完全保留了算出来的是 排列数。上一题代码求组合外层是nums。当外层固定是1时所有的1都只能被最先放入背包。效果1永远排在2和3的前面打乱了原始顺序算出来的是 组合数。公式都是dp[j] dp[j - nums[i]]仅仅是for循环换了个位置结果就截然不同这就是动态规划的美丽与恐怖之处。3.if(j nums[i])的必要性在求组合数时我们可以直接把内层循环写成for(int j coins[i]; j amount; j)省去if判断。但在求排列数时不能这么写。因为外层循环是在遍历j而nums[i]在内层每次i变化时nums[i]都不同所以必须在内部用if来做越界保护。您的处理非常严谨。57. 爬楼梯第八期模拟笔试题目描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢注意给定 n 是一个正整数。输入描述输入共一行包含两个正整数分别表示n, m输出描述输出一个整数表示爬到楼顶的方法数。输入示例3 2输出示例3#include iostream #include vector using namespace std; int main(){ int n, m; cin n m; // n: 目标台阶数(背包容量), m: 一次最多爬的步数(物品范围) // 1. 定义 DP 数组 // dp[j] 表示爬到第 j 阶有多少种不同的排列方法 vectorint dp(n 1, 0); // 2. 初始化 // 爬到第 0 阶起点有一种方法就是原地不动 dp[0] 1; // 3. 状态转移 // 【核心】求排列数外层必须是背包容量台阶 j内层是物品步数 i for(int j 1; j n; j){ for(int i 1; i m; i){ if(j i){ // 递推公式累加方案数 // 爬到 j 阶的方法数 爬到 j-i 阶的方法数 dp[j] dp[j - i]; } } } cout dp[n]; return 0; }总结1. 为什么必须是“外层 j内层 i”如果反过来写外层i内层j比如m2外层i1时算出的全是以1开头的序列如1,1,1...或1,2,1...。外层i2时算出的全是以2开头的序列如2,1,1...。这就变成了 组合数先走 1 后走 2和先走 2 后走 1 被当成同一种。但爬楼梯显然讲究顺序先跨 1 步再跨 2 步和先跨 2 步再跨 1 步是两种不同的爬法所以必须用 外层 j 内层 i 来求排列数。2. 与纯背包题的细微差别纯背包题给你一个数组如[1, 5, 2]数组里的元素是固定的可能无序。本题隐含的数组是[1, 2, 3, ..., m]这是一个连续递增的序列。但不管物品是乱序还是连续递增只要是求排列数模板就绝对不能变。