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,v;
cin>>n>>v;
vector<int> wi(n);
vector<int> vi(n);
for(int i=0;i<n;i++){
cin>>wi[i]>>vi[i];
}
vector<vector<int>> dp(n,vector<int>(v+1,0));
for(int j = wi[0];j<=v;j++){
dp[0][j] =dp[0][j-wi[0]]+vi[0];
}
for(int i=1;i<n;i++){
for(int j=0;j<=v;j++){
if(j<wi[i]) dp[i][j] = dp[i-1][j];
else{
dp[i][j] = max(dp[i-1][j],dp[i][j-wi[i]]+vi[i]);
}
}
}
cout<<dp[n-1][v]<<endl;
return 0;
}📊 DP数组定义
cpp
vector<vector<int>> dp(n, vector<int>(v+1, 0));
dp[i][j]：考虑前i种物品，背包容量为j时的最大价值注意：这里"种"很重要，因为每种物品可以选多次
🔄 状态转移逻辑
1. 初始化第一行（只考虑第一种物品）：
cpp
for(int j = wi[0]; j <= v; j++){
dp[0][j] = dp[0][j - wi[0]] + vi[0];
}
对于第一种物品，从它能装下的最小容量开始
dp[0][j] = dp[0][j - wi[0]] + vi[0]：不断添加第一种物品比如：物品重量2，价值3
dp[0][2] = 3（装1个）dp[0][4] = dp[0][2] + 3 = 6（装2个）dp[0][6] = dp[0][4] + 3 = 9（装3个）
2. 处理其他物品：
cpp
for(int i = 1; i < n; i++) {
for(int j = 0; j <= v; j++) {
if(j < wi[i]) {
dp[i][j] = dp[i-1][j]; // 装不下，继承之前的值
} else {
// 关键选择：不选当前物品 vs 选当前物品（可多个）
dp[i][j] = max(dp[i-1][j], dp[i][j - wi[i]] + vi[i]);
}
}
}
🎯 关键选择逻辑
cpp
max(dp[i-1][j], dp[i][j - wi[i]] + vi[i])
dp[i-1][j]：不选第i种物品，价值等于前i-1种物品的最大价值dp[i][j - wi[i]] + vi[i]：选第i种物品dp[i][j - wi[i]]：选了之后剩余容量的最大价值+ vi[i]：加上当前物品的价值注意：这里用
dp[i]而不是dp[i-1]，意味着可以重复选当前物品
518. 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10] 输出：1
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<uint> 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];
}
};🧠 解题思路
1. DP数组定义
cpp
vector<uint> dp(amount + 1, 0);
dp[j]：凑成金额j的硬币组合数使用
uint防止大数相加溢出（很好的考虑！）
2. 初始化
cpp
dp[0] = 1;
关键：金额为0时，只有1种组合方式（什么都不选）
这是动态规划的基准情况
3. 核心算法
cpp
for (int i = 0; i < coins.size(); i++) { // 遍历物品（硬币）
for (int j = coins[i]; j <= amount; j++) { // 遍历背包（金额）
dp[j] += dp[j - coins[i]];
}
}
🔍 详细解释
为什么这样遍历？
外层循环遍历硬币，内层循环遍历金额（正序）：
外层循环硬币：确保组合的顺序性，避免重复计算排列
先考虑用1元硬币，再考虑用2元硬币...
这样
{1,2}和{2,1}不会被重复计算
内层正序遍历：允许硬币重复使用
计算
dp[j]时，dp[j - coins[i]]可能已经包含当前硬币实现了"无限次使用"的效果
状态转移方程
cpp
dp[j] += dp[j - coins[i]];
含义：要凑金额j，可以在凑出金额
j - coins[i]的基础上，再添加一个coins[i]硬币（理解一下）相加：累计所有可能的组合方式
377. 组合总和 Ⅳ
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<uint> dp(target+1,0);
dp[0 ] = 1;
for(int i = 1;i<=target;i++){
for(int j =0;j<nums.size();j++){
if(nums[j]<=i){
dp[i] +=dp[i-nums[j]];
}
}
}
return dp[target];
}
};这个题就是上一个题换一下物品，和背包的顺序就好了，排列先背包，组合先物品。
57. 爬楼梯（第八期模拟笔试）
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述
输入共一行，包含两个正整数，分别表示n, m
输出描述
输出一个整数，表示爬到楼顶的方法数。
输入示例
3 2输出示例
3提示信息
数据范围：
1 <= m < n <= 32;
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶段
- 1 阶 + 2 阶
- 2 阶 + 1 阶