代码随想录算法训练营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;}