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

代码随想录 | Day46

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 今日学习目标
  • 一、算法题
    • 1.完全背包问题
    • 2.零钱兑换 II
    • 3.组合总和 Ⅳ
  • 学习及参考书籍


今日学习目标

完全背包问题
零钱兑换 II(518)
组合总和 Ⅳ(377)

一、算法题

1.完全背包问题

题目:
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。
每种物品有无限个,所以遍历的顺序要从小到大遍历

// 先遍历物品,再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

2.零钱兑换 II

题目:
给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

代码:

lass Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);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.组合总和 Ⅳ

题目:
给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 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 <= 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];}
};

学习及参考书籍

代码随想录

相关文章:

代码随想录 | Day46

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 今日学习目标一、算法题1.完全背包问题2.零钱兑换 II3.组合总和 Ⅳ 学习及参考书籍 今日学习目标 完全背包问题 零钱兑换 II&#xff08;518&#xff09; 组合总和…...

word行内插入mathtype 公式后行距变大解决办法

现象 word行内插入mathtype 公式后行距变大 解决方法 选中要进行操作的那些行&#xff0c;依次单击菜单命令“格式→段落”&#xff0c;打开“段落”对话框&#xff1b;单击“缩进和间距”选项卡&#xff0c;将间距的“段前”和“段后”都调整为“0行”&#xff1b;将“如果…...

直播预告 | YashanDB 2023年度发布会正式定档11月2日,邀您共同见证国产数据库发展实践!

11月2日&#xff0c;YashanDB 2023年度发布会将于云端直播开启&#xff0c;发布会以 「惟实励新」 为主题&#xff0c;邀请企业用户、合作伙伴、广大开发者共同见证全新产品与解决方案。届时发布会将在墨天轮社区同步进行&#xff0c;欢迎大家报名&#xff01; 惟实求真。Yasha…...

一文读懂WebClient和RestTemplate的差异

自 Spring 5 以来&#xff0c;WebClient已成为Spring WebFlux的一部分&#xff0c;并且是发出 HTTP 请求的首选方式。它是经典RestTemplate的首选替代方案&#xff0c;后者自 Spring 5.0 以来一直处于维护模式。 本文将讨论 Spring WebClient和RestTemplate类之间的主要区别。…...

如何使用SpringBoot处理全局异常

如何使用SpringBoot处理全局异常 使用ControllerAdvice 和 ExceptionHandler处理全局异常 参考&#xff1a; ControllerAdvice ResponseBody Slf4j public class ExceptionHandler {ResponseStatus(HttpStatus.OK)org.springframework.web.bind.annotation.ExceptionHandler…...

【2023CANN训练营第二季】——通过一份入门级算子开发代码了解Ascend C算子开发流程

本次博客讲解的代码是Gitee代码仓的Ascend C加法算子开发代码&#xff0c;代码地址为&#xff1a; quick-start 打开Add文件&#xff0c;可以看到文件结构如下&#xff1a; 其中add_custom.cpp是算子开发的核心文件&#xff0c;包括了核函数的实现&#xff0c;展示了如何在Asc…...

建模仿真软件 Comsol Multiphysics mac中文版软件介绍

COMSOL Multiphysics mac是一款全球通用的基于高级数值方法和模拟物理场问题的通用软件&#xff0c;拥有、网格划分、研究和优化、求解器、可视化和后处理、仿真 App等相关功能&#xff0c;轻松实现各个环节的流畅进行&#xff0c;它能够解释耦合或多物理现象。 附加产品扩展了…...

深入理解强化学习——强化学习的历史:近代强化学习的发展

分类目录&#xff1a;《深入理解强化学习》总目录 在《深入理解强化学习——强化学习的历史》前面的文章中我们讨论了最优控制和试错学习学习的思想&#xff0c;接下来&#xff0c;我们将讨论一些在20世纪60年代和70年代&#xff0c;在试错学习计算和理论研究被相对忽视的时候&…...

移动端ViT新利器!苹果提出稀疏专家混合模型Mobile V-MoEs

文章链接&#xff1a;https://arxiv.org/abs/2309.04354 最近&#xff0c;专家混合模型MoE受到了学术界和工业界的广泛关注&#xff0c;其能够对任意输入来激活模型参数中的一小部分来将模型大小与推理效率分离&#xff0c;从而实现模型的轻量化设计。目前MoE已经在自然语言处理…...

【linux系统】服务器安装Pycharm

文章目录 安装pycharm步骤1. 进入pycharm官网2. 上传到服务器3. 安装过程 摘要&#xff1a;pycharm是Python语言的图形化开发工具。因为如果在Linux环境下的Python shell 中直接进行编程&#xff0c;其无法保存与修改&#xff0c;在大型项目当中这是很不方便的&#xff0c;而py…...

便利连锁:如何增加收益?教你一招轻松搞定!

自动售货机&#xff0c;作为零售行业的一项颠覆性技术&#xff0c;正逐渐改变着我们的购物方式和商业格局。这一创新技术不仅重新定义了零售业务模式&#xff0c;还为企业提供了更多的机会来满足不断演变的消费者需求。 客户案例 便利连锁店 成都某便利连锁店面临一系列挑战&am…...

STM32-程序占用内存大小计算

STM32中程序占用内存容量 Keil MDK下Code, RO-data,RW-data,ZI-data这几个段: Code存储程序代码。 RO-data存储const常量和指令。 RW-data存储初始化值不为0的全局变量。 ZI-data存储未初始化的全局变量或初始化值为0的全局变量。 占用的FlashCode RO Data RW Data; 运行消…...

鱼眼图像去畸变python / c++

#鱼眼模型参考链接 本文假设去畸变后的图像与原图大小一样大。由于去畸变后的图像符合针孔投影模型&#xff0c;因此不同的去畸变焦距得到不同的视场大小&#xff0c;且物体的分辨率也不同。可以见上图&#xff0c;当焦距缩小为一半时&#xff0c;相同大小的图像&#xff08;横…...

文心一言简单体验

百度正式发布文心一言&#xff0c;文心一言 这里的插件模式挺有意思&#xff1a; 测试了一下图解说明&#xff0c;随意上传了一张图片&#xff1a; 提供图解让反过来画&#xff0c;抓住了部分重点&#xff0c;但是还是和原图有比较大的差异&#xff01; 百宝箱 暂未逐个体验&am…...

css正确的语法

Cascading Style Sheets (CSS) 是一种用于定义网页元素外观和样式的标记语言。以下是正确的 CSS 语法要点&#xff1a; 选择器 (Selector): 选择器用于指定要应用样式的 HTML 元素。例如&#xff0c;选择器可以是标签名、类名、ID、属性等。例如&#xff1a; 标签名选择器&…...

【PG】PostgresSQL角色管理

目录 角色概念 查询现有角色 列出当前角色 创建角色 删除角色 更改角色 创建角色举例 预定义角色 角色属性 登陆角色 超级用户角色 创建数据库角色 创建role角色 复制角色 创建带有密码的角色 角色成员关系 角色组概念 角色组增加成员 角色组移除成员 删除角…...

百度智能云获评Forrester中国市场人工智能/机器学习平台领导者

写在前面百度智能云AI平台&#xff0c;打造企业智能化转型的基础设施大模型时代&#xff0c;百度智能云AI平台迎来全面升级 写在前面 日前&#xff0c;国际权威咨询机构 Forrester 发布了最新的《The Forrester Wave™&#xff1a;中国市场人工智能/机器学习平台厂商评测&…...

基于java+swing+mysql实现的仓库商品管理系统

JavaSwingmysql用户信息管理系统 一、系统介绍二、功能展示三、项目相关3.1 乱码问题3.2 如何将GBK编码系统修改为UTF-8编码的系统&#xff1f; 四、其它1.其他系统实现 五、源码下载 一、系统介绍 本系统实现了两个角色层面的功能&#xff0c;管理员可以管理用户、仓库、商品…...

深入理解Spring Boot AOP:CGLIB代理与JDK动态代理的完全指南

深入理解Spring Boot AOP&#xff1a;CGLIB代理与JDK动态代理的完全指南 前言第一&#xff1a;AOP和代理模式AOP&#xff08;面向切面编程&#xff09;&#xff1a;代理模式&#xff1a; 第二&#xff1a;深入分析CGLIB代理&#xff0c;包括其实现原理和内部机制CGLIB的实现原理…...

【无标题】读书笔记之《智能化社会:未来人们如何生活、相爱和思考》

《智能化社会&#xff1a;未来人们如何生活、相爱和思考》&#xff1a;Digital vs Human_ how well live, love, and think in the future &#xff0c;由中信出版社于2017年06月出版。作者是澳大利亚的理查德沃特森(Richard Watson)。Richard Watson在伦敦帝国理工学院从事未来…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...