当前位置: 首页 > 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在伦敦帝国理工学院从事未来…...

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 //第一…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...