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

代码随想录算法训练营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;}
http://www.lryc.cn/news/439260.html

相关文章:

  • Java-idea小锤子图标
  • 最强神器Typora 2024(亲测有效)| Markdown 工具推荐
  • 【时时三省】tessy 单元测试 集成测试 专栏 文章阅读说明
  • 力扣刷题(6)
  • TiDB 扩容过程中 PD 生成调度的原理及常见问题丨TiDB 扩缩容指南(一)
  • 匿名管道详解
  • 深度解读MySQL意向锁的工作原理机制与应用场景
  • ZYNQ TCP 协议的远程更新 QSPI Flash
  • 告别繁琐粘贴,CleanClip Mac 版,让复制粘贴变得简单快捷!粘贴队列功能太强大了!
  • 前端基础知识(HTML+CSS+JavaScript)
  • 算力服务器和GPU服务器的区别是什么?
  • 获取Live2d模型
  • 软考架构-层次架构风格
  • Unity射击游戏开发教程:(35)轰炸敌人
  • 【网络】高级IO——select版本TCP服务器
  • 【C++】学完c语言后的c++基础知识补充!(命名空间、输入和输出、缺省函数、函数重载、引用、内联函数代替宏、nullptr代替NULL)
  • uniapp自定义导航栏以及页面加背景
  • MacOS Sonoma(14.x) 大写模式或中文输入法下的英文模式,光标下方永远会出现的CapsLock箭头Icon的去除办法
  • C#基础(10)变长参数和参数默认值
  • Vue转React开发经验分享——hooks写法如何触发react生命周期、如何触发数据更新?
  • 算法入门-贪心1
  • element-plus的面包屑组件el-breadcrumb
  • 推荐几个网盘资源站给大伙,找资源更方便
  • 【Qt】Qml界面中嵌入C++ Widget窗口
  • Python快速入门 —— 第五节:接口开发
  • 利用secureCRT向虚拟机发送文件(secureCRT安装使用教程)
  • AI杂七杂八系列(1)——工程篇
  • 学习大数据DAY58 增量抽取数据表
  • HTTPTomcat
  • Python数据分析-Matplotlib快速入门