代码随想录算法训练营day37

1.携带研究材料

1.1 题目

52. 携带研究材料（第七期模拟笔试）

1.2 题解

#include <iostream>
#include <functional>
#include <vector>
using namespace std;int main()
{//输入相关信息int classes, cabaity;cin >> classes >> cabaity;vector<int> weights(classes,0);vector<int> values(classes,0);for (int i = 0; i < classes; i++){cin >> weights[i]>>values[i];}//确定dp数组dp[j]代表背包容量为j所带的最大价值为dp[j]vector<int> dp(cabaity + 1,0);//确定递推逻辑//dp[j]=max(dp[j]+dp[j-weights[i]]+values[j]);//初始化dp[0] = 0;//遍历物品for (int i = 0; i < classes; i++){//遍历背包for (int j = weights[i]; j <=cabaity ; j++){dp[j] = max(dp[j] , dp[j - weights[i]] + values[i]);}}cout<< dp[cabaity]<<endl;return 0;
}

2.零钱兑换

2.1 题目

. - 力扣（LeetCode）

2.2 题解

class Solution {
public:int change(int amount, vector<int>& coins) {//确定dp数组，dp[j]表示总和为j凑成的方法数vector<int> dp(amount + 1);//确定递推逻辑//dp[j]+=dp[j-coins[i]]//初始化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];}
};

3.组合总和IV

3.1 题目

. - 力扣（LeetCode）

3.2 题解

class Solution 
{
public:int combinationSum4(vector<int>& nums, int target) {vector<int> 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];}
};

4.爬楼梯（进阶版）

4.1 题目

57. 爬楼梯（第八期模拟笔试）

4.2 题解

int main()
{//总的台阶数为n，每次最多能爬的楼梯为mint n, m;cin >> n >> m;//确定dp数组//dp[j]表示爬完j阶楼梯的方法数vector<int> dp(n + 1, 0);dp[0] = 1;//求的是组合数，先遍历背包，再遍历物品for (int j = 1; j <= n; j++){for (int i = 1; i <= m; i++){if (j - i >= 0)dp[j] += dp[j - i];}}cout << dp[n] << endl;return 0;}