代码随想录算法训练营第四十四天|70. 爬楼梯(进阶版)

news/2024/7/20 17:52:15/文章来源:https://blog.csdn.net/qq_55999494/article/details/139126382

70. 爬楼梯(进阶版)

多重背包问题,代取商品就是从1:m的数组,背包的容量就是n,由于是求方法数,所以递推公式为

dp[j]+=dp[j-nums[i]];

因为是排序问题,所以需要先循环容量,后循环商品

322. 零钱兑换

此题是求最小的情况,也就是把背包装满所用的最小的商品数,

初始化中除了dp[0]是正常初始化,其他的dp[i]值都采用INT_MAX进行初始化

因为无论排列和组合,求出的最小商品数都是相同的,所以可以先循环容量,再循环商品,反过来也行。
循环的递推公式为:

if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

首先我们需要求最小值,和求最大值的情况差不多,只是把max换成了min

dp[j - coins[i]] != INT_MAX这个条件是确保在利用dp[j - coins[i]]得到dp[j]的过程中,所使用的一定是更新过的dp[j - coins[i]],防止dp[j - coins[i]]为未更新过的初始值,影响dp[j]的正常推导。

279.完全平方数

与上题相同,商品数组是由平方项构成的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1054217.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

密码学基础概念

加密性 什么是加密? 1.对原有的明文数据,执行某种运算,得到密文数据。 2.密文数据对于未授权人员而言,在一定上程度上加大了解读的难度 3.加密功能用于实现机密性 什么是密钥? 1.如同持有保险柜钥匙才能打开保险柜…

如何在Spring Boot中整合PageHelper实现分页功能

1.前言 在开发web应用程序时,经常会遇到需要对数据库中的数据进行分页查询的情况。为了简化分页查询的实现过程,我们可以利用PageHelper这个优秀的分页插件来实现分页功能。本文将介绍如何在Spring Boot项目中整合PageHelper,并演示如何使用它…

Thinkphp3.2.3网站后台不能访问如何修复

我是使用Thinkphp3.2.3新搭建的PHP网站,但是网站前台可以访问,后台访问出现如图错误: 由于我使用的Hostease的Linux虚拟主机产品默认带普通用户权限的cPanel面板,对于上述出现的问题不清楚如何处理,因此联系Hostease的…

深入分析 Android Activity (十一)

文章目录 深入分析 Android Activity (十一)1. Activity 的内存管理和优化1.1 内存泄漏的常见原因1.2 避免内存泄漏的方法1.3 内存泄漏检测工具 2. Activity 的配置变更处理2.1 处理配置变更2.2 保存和恢复状态2.3 使用 ViewModel 3. Activity 的测试3.1 单元测试3.2 UI 测试 4…

Centos安装nvm管理node版本(让安装变得可控又快捷)

Centos安装nvm管理node版本(让安装变得可控又快捷) 没有找到一个对的人,有可能是你没有走对那条路,也有可能是你没有睁开眼睛,而更大的可能是,你根本就没有出发去找。 安装说明 nvm安装目录:/us…

[ue5]建模场景学习笔记(1)——混合材质

卷首:这部分会记录建模场景等相关学习内容,与ue引擎学习笔记不同的是,可能会略过一些基础内容,因为部分知识在blender中已经学习过了,不再继续记录。 1.需求分析: 想构建一个山地的场景,在ue5中…

为什么要学习c++?

你可能在想,“C?那不是上个时代的产物吗?” 哎呀,可别小看了这位“老将”,它在21世纪的科技舞台上依旧光芒万丈,是许多尖端技术不可或缺的基石! 1. 无可替代 c源于c语言,它贴近于硬…

gif帧数修改怎么操作?一键掌握GIF帧数修改技巧!

gif帧数修改怎么操作?在数字化信息爆炸的时代,GIF动图因其生动有趣的特性而备受广大网友喜爱。然而,很多时候我们可能会遇到GIF动图帧数过多或过少,导致动画效果不尽如人意的情况。那么,如何对GIF动图的帧数进行修改呢…

如何利用Firebase Hosting来托管网站

文章目录 如何利用Firebase Hosting来托管网站前提条件详细步骤1. 安装 Firebase CLI2. 登录 Firebase3. 初始化 Firebase 项目4. 准备网站文件5. 部署到 Firebase6. 配置自定义域名(可选) 常见问题 如何利用Firebase Hosting来托管网站 以下是更详细的…

【Python】进阶学习:pandas--describe()函数的使用介绍

🐍【Python】进阶学习:pandas——describe()函数的使用介绍 🌈 个人主页:高斯小哥 🔥 高质量专栏:Matplotlib之旅:零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&am…

关于锂电池短路测试

了解锂电池短路测试 电池短路试验测试标准有哪些?宏展告诉你 - 哔哩哔哩 (bilibili.com) 电池电芯上架亚马逊美国站认证标准和要求UL1642测试 - 知乎 (zhihu.com) CR123A电池的短路试验: CR123A电池为例_锂锰电池所需通过的安全性能测试_纽扣电池_锂锰电池_松下电…

若依启动run-modules-system.bat报错问题解决方案

在启动run-modules-system.bat时遇到了一些问题,在网上搜索无果后,排查解决完毕 1.启动nacos时,报错如下 Error creating bean with name grpcClusterServer: Invocation of init method failed; nested exception is java.io.IOException: Failed to bind to address 0.0.0.0…

Linux Tcpdump抓包入门

Linux Tcpdump抓包入门 一、Tcpdump简介 tcpdump 是一个在Linux系统上用于网络分析和抓包的强大工具。它能够捕获网络数据包并提供详细的分析信息,有助于网络管理员和开发人员诊断网络问题和监控网络流量。 安装部署 # 在Debian/Ubuntu上安装 sudo apt-get install…

《TCP/IP网络编程》(第十二章)I/O复用(1)

本章将讨论实现并发服务器的第二种办法,基于I/O复用的服务器端构建。 I/O复用它允许单个进程或线程同时处理多个输入/输出(I/O)操作,而无需为每个I/O操作创建一个独立的线程或进程。这种技术可以显著提高应用程序的效率和性能&…

每日复盘-20240528

今日重点关注: 20240528 六日涨幅最大: ------1--------300956--------- 英力股份 五日涨幅最大: ------1--------301361--------- 众智科技 四日涨幅最大: ------1--------301361--------- 众智科技 三日涨幅最大: ------1--------301361--------- 众智科技 二日涨…

【全开源】CMS内容管理系统源码(ThinkPHP+FastAdmin)

基于ThinkPHPFastAdmin的CMS内容管理系统,自定义内容模型、自定义单页、自定义表单、专题、统计报表、会员发布等 提供全部前后台无加密源代码和数据库私有化部署,UniAPP版本提供全部无加密UniAPP源码。 ​构建高效内容管理的基石 一、引言&#xff1a…

如何将 Langfuse 链接到自有 PostgreSQL 数据库并升级 PostgreSQL 版本

在本文中,我们将介绍如何将 Langfuse 应用程序链接到自有的 PostgreSQL 数据库,并升级 PostgreSQL 以支持 jsonb 类型。 前提条件 运行 CentOS 7 的服务器已安装的 PostgreSQL 9.2 或更低版本需要将 Langfuse 连接到自有数据库,并升级 PostgreSQL 以支持 jsonb 类型1. 将 La…

小程序使用vant组件库

一:下载组件库 在小程序内npm下载的包 vant组件库官网:快速上手 - Vant Weapp (youzan.github.io) 1)首先有有package.json文件,没有的话则先初始化 即使通过package.json去下载包,也需要有,可以观察下载的包. 2)下载包 3)构建npm包 下载包之后存储在node_modules内,但是我们…

R包Colorfindr识别图片颜色|用刀剑神域方式打开SCI科研配色

1.前言 最近忙里偷闲,捣鼓一下配色,把童年回忆里的动漫都搬进来,给科研信仰充值吧~ 提取颜色之前写过一个Py的,那个很准确不过调参会有点麻烦。这里分享一个比较懒人点的R包吧,虽然会有一定误差&#xff…

yolox-何为混合精度计算AMP?

何为AMP? 全称:Automatic mixed precision自动混合精度。 功能:在神经网络推理过程中,实现针对不同层采用不同的数据精度进行计算,从而实现节省显存和加速训练的目的。 此处提到的不同数据精度包括:32位浮…