当前位置：首页 > news >正文

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

news 2026/4/15 7:47:13

52. 携带研究材料（第七期模拟笔试）
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。
小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。
输入描述
第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量
接下来包含 n 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值
输出描述
输出一个整数，表示最大价值。
输入示例
4 5
1 2
2 4
3 4
4 5
输出示例
10

#include <iostream> #include <vector> using namespace std; int main(){ int n, bagSize; cin >> n >> bagSize; vector<int> w(n + 1); vector<int> v(n + 1); // 读入物品的重量和价值（您的代码从下标 0 开始读入，完全没问题） for(int i = 0; i < n; i++) cin >> w[i] >> v[i]; // 1. 定义 DP 数组 // dp[j] 表示容量为 j 的背包能装下的最大价值 vector<int> 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, vector<int>& coins) { int n = coins.size(); // 1. 定义 DP 数组 // dp[j] 表示：凑成总金额 j 的硬币组合数 // 【高光细节】：这里必须用 uint64_t 或者 long long // 因为组合数会非常大，普通的 int 会在 LeetCode 的测试用例中溢出导致错误！ vector<uint64_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(vector<int>& nums, int target) { int n = nums.size(); // 1. 定义 DP 数组 // dp[j] 表示：凑成目标和为 j 的排列总数 // 依然使用 uint64_t 防止极端用例下的整型溢出 vector<uint64_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 阶有多少种不同的排列方法 vector<int> 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; }