当前位置: 首页 > 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…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...