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

代码随想录算法训练营Day38||完全背包问题、leetcode 518. 零钱兑换 II 、 377. 组合总和 Ⅳ 、70. 爬楼梯 (进阶)

一、完全背包问题

        相较于01背包,完全背包的显著特征是每个物品可以用无数次,遍历顺序也不需要为了保证每个物品只去一次而倒序遍历。

        

#include<iostream>
#include<vector> 
using namespace std;
int main(){int N,V;cin>>N>>V;vector<int>weight(N+1,0);vector<int>value(N+1,0);for(int i=0;i<N;i++){cin>>weight[i]>>value[i];}vector<int>dp(V+1,0);for(int i=0;i<N;i++){for(int j=weight[i];j<=V;j++){dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}cout<<dp[V]<<endl;return 0;
}

二、零钱兑换

        (一)dp数组含义:dp[j]为凑成j元可以的方法数

        (二)递推公式:dp[j]+=dp[j-coins[i]]把数组中第一个元素所能组成的方法数一直加到最后一个元素所能组成的方法数。

        (三)初始化:dp[0]=1

        (四)完全背包,正向遍历背包,组合问题选择先物品后背包。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int>dp(amount+1,0);//dp[j]为凑成j元的组合数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];}
};

三、组合总和Ⅳ

        本题是排列问题,排列问题与组合问题的区别就是遍历顺序不同

        

        (一)dp数组含义:dp[j]为凑成总和为j,可以的方法数

        (二)递推公式:dp[j]+=dp[j-nums[i]]把数组中第一个元素所能组成的方法数一直加到最后一个元素所能组成的方法数。

        (三)初始化:dp[0]=1

        (四)完全背包,正向遍历背包,排列问题先背包后物品

        

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int>dp(target+1,0);dp[0]=1;// for(int i=0;i<nums.size();i++){//     for(int j=nums[i];j<=target;j++){//         dp[j]+=dp[j-nums[i]];//     }// }for(int j=0;j<=target;j++){for(int i=0;i<nums.size();i++){if(j>=nums[i]&&dp[j]<INT_MAX-dp[j-nums[i]])dp[j]+=dp[j-nums[i]];}}return dp[target];}
};

四、爬楼梯 (完全背包法)

#include<iostream>
#include<vector>
using namespace std;
int main(){int n,m;cin>>n>>m;vector<int>pathlength;for(int i=0;i<m;i++){pathlength.push_back(i+1);}vector<int>dp(n+1,0);dp[0]=1;for(int j=0;j<=n;j++){for(int i=0;i<m;i++){if(j>=pathlength[i]){dp[j]+=dp[j-pathlength[i]];}}}cout<<dp[n]<<endl;return 0;
}

相关文章:

代码随想录算法训练营Day38||完全背包问题、leetcode 518. 零钱兑换 II 、 377. 组合总和 Ⅳ 、70. 爬楼梯 (进阶)

一、完全背包问题 相较于01背包&#xff0c;完全背包的显著特征是每个物品可以用无数次&#xff0c;遍历顺序也不需要为了保证每个物品只去一次而倒序遍历。 #include<iostream> #include<vector> using namespace std; int main(){int N,V;cin>>N>>V…...

超越链端:Web3的无边界技术革命

Web3&#xff0c;作为互联网技术的第三代变革&#xff0c;正以其去中心化、开放透明的特性&#xff0c;重新定义着我们的数字生活。在这一背景下&#xff0c;“链端”概念逐渐成为热点&#xff0c;意味着我们不仅仅局限于区块链技术本身&#xff0c;而是探索其在更广泛领域的应…...

127. Go反射基本原理

文章目录 反射基础 - go 的 interface 是怎么存储的&#xff1f;iface 和 eface 的结构体定义&#xff08;runtime/iface.go&#xff09;&#xff1a;_type 是什么&#xff1f;itab 是什么&#xff1f; 反射对象 - reflect.Type 和 reflect.Value反射三大定律Elem 方法reflect.…...

提高PDF电子书的分辨率

解决方法出处 1. 安装ImageMagick brew install imagemagick brew install ghostscript2. 按流程进行 convert -density 600 your_pdf_filename.pdf output-%02d.jpg convert output*.jpg -normalize -threshold 80% final-%02d.jpg convert final*.jpg my_new_highcontras…...

Spring Cloud全解析:注册中心之zookeeper注册中心

zookeeper注册中心 使用zookeeper作为注册中心就不需要像eureka一样&#xff0c;在写一个eureka-server的服务了&#xff0c;因为zookeeper本身就是一个服务端&#xff0c;只需要编写需要进行服务注册的客户端即可 依赖 <!-- zookeeper 注册中心 --> <dependency&g…...

解决戴尔台式电脑休眠后无法唤醒问题

近期发现有少量戴尔的台式机会有休眠后无法唤醒的问题&#xff0c;具体现象就是电脑在休眠后&#xff0c;电源指示灯以呼吸的频率闪烁&#xff0c;无论怎么点鼠标和键盘都没有反应&#xff0c;并且按开机按钮也没法唤醒&#xff0c;只能是长按开机键强制关机再重启才行&#xf…...

MySQL运维-分库分表

介绍 问题分析 拆分策略 垂直拆分 水平拆分 实现技术 Mycat概述 介绍 概念介绍 Mycat配置 schema.xml schema标签 schema标签&#xff08;table&#xff09; datanode标签 datahost标签 rule.xml sever.xml system标签 user标签 Mycat分片 分片规则-范围 分片规则-取模 分…...

AGX orin硬件设计

AGX orin简介 ​ 从硬件组成来说&#xff0c;AGX orin可以分为核心板和扩展板。 核心板 ​ 核心板就是英伟达原装板卡&#xff0c;如下图所示&#xff1a; ​ 核心板分为32G内存版本和64内存版本&#xff0c;两个版本除去内存不同之外&#xff0c;CPU也略有差异。核心板通过…...

AI大模型开发——2.深度学习基础(1)

学习大模型开发之前&#xff0c;我们需要有足够的储备知识&#xff0c;类似于基础的python语法相信大家也都是十分熟悉了。所以笔者也是考虑了几天决定先给大家补充一些深度学习知识。 首先问大家一个问题&#xff0c;学习大模型之前为什么要先学习深度学习知识呢&#xff1f; …...

go语言day22 gin-vue-admin全栈项目的依赖安装

flipped-aurora/gin-vue-admin: &#x1f680;ViteVue3Gin的开发基础平台&#xff0c;支持TS和JS混用。它集成了JWT鉴权、权限管理、动态路由、显隐可控组件、分页封装、多点登录拦截、资源权限、上传下载、代码生成器【可AI辅助】、表单生成器和可配置的导入导出等开发必备功能…...

PHP之docker学习笔记

Docker学习笔记 前言&#xff1a; 之前学过一遍忘了 那就再来一遍没啥好说的就是可以直接构建一个环境 然后方便部署官网 http://www.docker.com仓库 https://hub.docker.comDocker的基本组成 镜像 容器 仓库 安装与卸载 卸载 sudo yum remove docker \docker-client \dock…...

基于树莓派4B与STM32的UART串口通信实验(代码开源)

在现代嵌入式系统中&#xff0c;树莓派和STM32的结合使用已成为一种流行趋势&#xff0c;它们各自承担不同的角色&#xff0c;实现优势互补。树莓派以其强大的计算能力处理复杂算法&#xff0c;而STM32则以其高效的控制能力执行实际的硬件操作。本文将详细介绍如何实现基于树莓…...

【云服务器系列】基于华为云OBS实现Picgo和Typora的完美融合

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

IIC协议

一、IIC协议 1.1 IIC协议概述 IIC全称Inter-Integrated Circuit (集成电路总线) 是由PHILIPS(飞利浦)公司在80年代开发的两线式串行总线&#xff0c;用于连接微控制器及其外围设备。IIC属于半双工同步通信方式 特点 简单性和有效性。 由于接口直接在组件之上&#xff0c;…...

如何在linux系统上部署nginx

1&#xff09;首先去 nginx.org/download 官网下载你所需要的版本 我这里是下载的 nginx-1-23-3.tar.gz 2&#xff09;然后执行 yum -y install lrzsz 安装文件上传软件 执行 rz 选择你下载nginx的位置进行上传 yum -y install lrzsz 3&#xff09;执行 tar -zxvf nginx-1.23…...

香港网站服务器抵御恶意攻击的一些措施

香港网站服务器因为在互联网中扮演着重要的角色&#xff0c;因此也在面临着网络中各种恶意攻击的威胁&#xff0c;为了确保香港网站服务器的安全和稳定运行&#xff0c;可以通过安全措施来进行防御&#xff0c;本文就来分享一些香港网站服务器来抵御恶意攻击的关键措施。 一、网…...

实战:docker部署filesite.io完美解决家庭相册需求-2024.8.10(测试成功)

https://wiki.onedayxyy.cn/docs/filesite.io-photot-install-full...

美团到店面经

redis中大key引起的问题 1、阻塞请求 Big Key对应的value较大&#xff0c;我们对其进行读写的时候&#xff0c;需要耗费较长的时间&#xff0c;这样就可能阻塞后续的请求处理。Redis的核心线程是单线程&#xff0c;单线程中请求任务的处理是串行的&#xff0c;前面的任务完不成…...

【CSS入门】第五课 - font字体

这一节&#xff0c;我们说一说font这个字体。做网页开发&#xff0c;网页中几乎不可能没有文字的&#xff0c;为了使网页更漂亮&#xff0c;用户体验更好。人们可算是绞尽脑汁&#xff0c;其中一部分就是在字体上下的大功夫。 接下来&#xff0c;我们学习一下&#xff0c;font…...

STM32-门电路-储存器-寄存器-STM32f1-MCU-GPIO-总线-keil5-点led-寄存器编程

1、门电路 门电路组成简单加法器&#xff1a; 二进制对电路的影响&#xff1a; 0和1代表无和有&#xff1b; 以下图例&#xff0c;演示与门&#xff1a;左1右1输出1&#xff1b; 电平标准&#xff1a;使用不同的电压表示数字0和1&#xff1b; 高电平&#xff1a;1&#xff1…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...