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

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...