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

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...