day45第九章动态规划(二刷)
今日任务
- 70.爬楼梯(进阶)
- 322.零钱兑换
- 279.完全平方数
70.爬楼梯(进阶)
题目链接:
https://leetcode.cn/problems/climbing-stairs/description/
题目描述:
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示:
1 <= n <= 45
题解代码:
class Solution {
public://二刷复习动态规划,用完全背包地方式做一次int climbStairs(int n){vector<int> dp(n+1, 0); //定义dp数组,dp[i]表示爬到有i个台阶的楼顶,有dp[i]种方法dp[0] = 1; //初始化dp数组,dp[0]是其他数值的基础,所以要是1for(int i = 1; i <= n; i++){//遍历背包for(int j = 1; j <= 2;j++){//遍历物品,也就是台阶if(i-j >= 0){dp[i] += dp[i-j];}}}return dp[n];}//一刷动态规划 /*int climbStairs(int n) {//再用完全背包的方式做一次 vector<int> dp(n+1,0);//定义dp数组,dp[i]表示爬到有i个台阶的楼顶,有dp[i]种方法dp[0] = 1; //初始化dp数组,dp[0]是其他数值的基础,所以要是1for(int i = 1; i <= n;i++){ //遍历背包for(int j = 1; j <= 2; j++){ //遍历物品,也就是台阶if(i-j>=0){dp[i] += dp[i-j];}}}return dp[n];/*if(n <= 1){return n; }vector<int> dp(n+1); //定义dp数组,dp[i]代表到第i层有dp[i]种办法dp[1] = 1; //初始化dp数组,注意这里不初始化dp[0]dp[2] = 2;for(int i = 3; i <= n; i++){//注意i是从3开始的dp[i] = dp[i-1] + dp[i-2];//递推方程}return dp[n];*//* }*///二刷复习动态规划//斐波那契数列式完成/*int climbStairs(int n){if(n <= 1){return n;}vector<int> dp(n+1); //dp数组,dp[i]代表到第i层有dp[i]种方法dp[1] = 1;dp[2] = 2;for(int i = 3; i <= n; i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}*/
};
322.零钱兑换
题目链接:
https://leetcode.cn/problems/coin-change/description/
题目描述:
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins =[1, 2, 5], amount =11输出:3解释:11 = 5 + 5 + 1
示例 2:
输入:coins =[2], amount =3输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
题解代码:
class Solution {
public://二刷动规复习int coinChange(vector<int>& coins, int amount){vector<int> dp(amount+1, INT_MAX); //dp数组,dp[j]表示凑足总数为j所需要的钱币的最少个数为dp[j]dp[0] = 0; //初始化dp数组,dp[0]凑足总数为0所需的钱币最少个数为0个for(int i = 0; i < coins.size(); i++){//遍历物品for(int j = coins[i]; j <= amount; j++){//遍历背包if(dp[j-coins[i]] != INT_MAX){dp[j] = min(dp[j],dp[j-coins[i]]+1);}}}if(dp[amount] == INT_MAX){return -1;}return dp[amount];}//一刷动规复习/*int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1, INT_MAX); //dp数组,dp[j]表示凑足总数为j所需的钱币的最少个数为dp[j]dp[0] = 0;//初始化dp数组,dp[0]凑足总数为0所需的钱币的最少个数为0个for(int i = 0; i < coins.size(); i++){//遍历物品for(int j = coins[i]; j <= amount; j++){ //遍历背包if(dp[j-coins[i]] != INT_MAX){dp[j] = min(dp[j],dp[j-coins[i]]+1);}}}if(dp[amount] == INT_MAX){return -1;}return dp[amount];}*/
};
279.完全平方数
题目链接:
https://leetcode.cn/problems/perfect-squares/description/
题目描述:
给你一个整数 n
,返回 和为 n
的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
示例 1:
输入:n =12输出:3
解释:12 = 4 + 4 + 4
示例 2:
输入:n =13输出:2
解释:13 = 4 + 9
提示:
1 <= n <= 104
题解代码:
class Solution {
public://二刷动规复习int numSquares(int n){vector<int> dp(n+1, INT_MAX); //定义dp数组,dp[j]表示和为j的完全平方数的最小数量dp[j]dp[0] = 0; //和为0的完全平方数的最小数量为dp[0]for(int i = 0; i <= n; i++){//遍历背包for(int j = 1; j*j <= i; j++){//遍历物品dp[i] = min(dp[i], dp[i-j*j]+1);}}return dp[n];}//一刷动规/*int numSquares(int n) {vector<int> dp(n+1,INT_MAX);//定义dp数组,dp[j]表示和为j的完全平方数的最小数量d[j]dp[0] = 0; //和为0的完全平方数的最小数量为dp[0]for(int i = 0; i <= n; i++){ //遍历背包for(int j = 1; j*j <= i; j++){ //遍历物品dp[i] = min(dp[i],dp[i-j*j]+1);}}return dp[n];}*/
};
总结
我们知道这是完全背包,
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
相关文章:
day45第九章动态规划(二刷)
今日任务 70.爬楼梯(进阶)322.零钱兑换279.完全平方数 70.爬楼梯(进阶) 题目链接: https://leetcode.cn/problems/climbing-stairs/description/ 题目描述: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不…...

第十四届蓝桥杯第三期模拟赛原题与详解
文章目录 一、填空题 1、1 找最小全字母十六进制数 1、1、1 题目描述 1、1、2 题解关键思路与解答 1、2 给列命名 1、2、1 题目描述 1、2、2 题解关键思路与解答 1、3 日期相等 1、3、1 题目描述 1、3、2 题解关键思路与解答 1、4 乘积方案数 1、4、1 题目描…...

client打包升级
目录 前言 一、client如何打包升级? 二、使用步骤 1.先进行改版本 2.执行打包升级命令 总结 前言 本文章主要记录一下,日常开发中,常需要进行打包升级的步骤。 一、client如何打包升级? # 升级发布版本 ## 修改版本 * 父p…...

Blazor_WASM之3:项目结构
Blazor_WASM之3:项目结构 Blazor WebAssembly项目模板可选两种,Blazor WebAssemblyAPP及Blazor WebAssemblyAPP-Empty 如果使用Blazor WebAssemblyAPP模板,则应用将填充以下内容: 一个 FetchData 组件的演示代码,该…...
OperWrt 包管理系统02
文章目录 OperWrt 包管理系统OPKG简介OPKG的工作原理OPKG命令介绍软件包的更新、安装、卸载和升级等功能软件包的信息查询OPKG配置文件说明OPKG包结构(.ipk)OPKG演示案例OperWrt 包管理系统 OPKG简介 OPKG(Open/OpenWrt Package)是一个轻量快速的软件包管理系统,是 IPKG…...

人人都学会APP开发 提高就业竞争力 简单实用APP应用 安卓浏览器APP 企业内部通用APP制作 制造业通用APP
安卓从2009年开始流程于手机、平板,已经是不争的非常强大生产力工具,更为社会创造非常高的价值,现在已经是202X年,已经十几年的发展,安卓平台已经无所不在。因此建议人人都学学APP制作,简易入门,…...

【自然语言处理】从词袋模型到Transformer家族的变迁之路
从词袋模型到Transformer家族的变迁之路模型名称年份描述Bag of Words1954即 BOW 模型,计算文档中每个单词出现的次数,并将它们用作特征。TF-IDF1972对 BOW 进行修正,使得稀有词得分高,常见词得分低。Word2Vec2013每个词都映射到一…...

LIME: Low-light Image Enhancement viaIllumination Map Estimation
Abstract当人们在低光条件下拍摄图像时,图像通常会受到低能见度的影响。除了降低图像的视觉美感外,这种不良的质量还可能显著降低许多主要为高质量输入而设计的计算机视觉和多媒体算法的性能。在本文中,我们提出了一种简单而有效的微光图像增…...
源码指标编写1000问4
4.问: 哪位老师把他改成分析家的,组合公式:猎庄敢死队别样红(凤翔) {猎庄敢死队} rsv:(c-llv(l,9))/(hhv(h,9)-llv(l,9))100; stickline(1,50,50,1,0),pointdot,Linethick2,colorff00; k:sma(rsv,3,1); d:sma(k,3,1); rsv1:(hhv(h,9.8)-c)/(hhv(h,9.8)-llv(l,9.8))1…...

Golang中GC和三色屏障机制【Golang面试必考】
文章目录Go v1.3 标记—清楚(mark and sweep)方法Go V1.5 三色标记法三色标记过程无STW的问题强弱三色不变式插入写屏障Go V1.8的三色标记法混合写屏障机制混合写屏障场景场景1:对象被一个堆对象删除引用,成为栈对象的下游场景2:对象被一个栈对象删除引用࿰…...

MOS FET继电器(无机械触点继电器)设计输入侧电源时的电流值概念
设计输入侧电源时的问题 机械式继电器、MOS FET继电器分别具有不同的特长。基于对MOS FET继电器所具小型及长寿命、静音动作等优势的需求,目前已经出现了所用机械式继电器向MOS FET继电器转化的趋势。 但是,由于机械式继电器与MOS FET继电器在产品结构…...

5. 驱动开发
文章目录一、驱动开发1.1 前言1.2 何谓驱动框架1.3 内核驱动框架中LED的基本情况1.3.1 相关文件1.3.2 九鼎移植的内核中led驱动1.3.3 案例分析驱动框架的使用1.3.4 典型的驱动开发行业现状1.4 初步分析led驱动框架源码1.4.1 涉及到的文件1.4.2 subsys_initcall1.4.3 led_class_…...
模板方法模式详解
模板方法模式(行为模式) 1. 模板方法模式介绍 父类定义算法骨架,细节的具体实现延迟到子类子类只是定义某些自己的个性化处理,但不改变执行顺序 2. 好处 减少代码冗余,共性抽取后算法流程更加清晰与规范降低流程性…...
关于 Lightweight process container,ChatGPT的答案
晓楚 Can you give me a list of process container? As an AI language model, I can provide you with a list of popular process containers, which are as follows: Docker Kubernetes Apache Mesos LXC OpenVZ systemd-nspawn rkt (Rocket) Linux Containers (LXC) Ga…...

机器学习和深度学习的综述
机器学习和深度学习的综述 1.1.1人工智能、机器学习、深度学习的关系 人工智能(Artificial Intelligence,AI)是最宽泛的概念,是研发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。由于这个定义…...

Synopsys Sentaurus TCAD系列教程之--Sprocess(SmallMOS_2D3D) 解析
SmallMOS_2D3D解析 #header## STI depth set sti_depth 0.15 ## Half STI width set sti_width sti_width ## Half gate length set gate_len <lg/2> ## SD length (from center) set sd_len [expr $gate_len0.05]#endheader## X lines line x location 0.0 spacing 0.…...

好使!NAS中傻瓜式配置反向代理及SSL证书,提升网络安全性!
对于有NAS或者有个人主机的朋友来说,将机器映射到外网是基本操作。 但是一般来说,能直接从外网访问的往往仅有80和443端口。事实上,运营商一般把家庭宽带的这两个端口都封了,所以如果我们想要从外网访问自己家中机器部署的服务&a…...
数据结构队列-先进先出
一,概述 队列这个概念非常好理解。你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。先进者先出,这就是典型的“队列”。 二,顺序队列和链式队列 队列和栈一样,也是一种…...
CentOS 7使用TiUP部署TiDB
本文主要是根据官方文档指导,结合实际主机情况,在Cent OS7上使用TiUP在线部署TiDB。 环境说明 类型操作系统版本配置中控机Deepin 20.34核CPU6G内存40G硬盘TiDB部署机Cent OS 7.38核CPU48G内存100硬盘网络情况中控机与外网相连,中控机与部署…...

java单元测试批处理数据模板【亿点点日志配合分页以及多线程处理】
文章目录引入相关资料环境准备分页查询处理,减少单次批量处理的数据量级补充亿点点日志,更易观察多线程优化查询_切数据版多线程_每个线程都分页处理引入 都说后端开发能顶半个运维,我们经常需要对大量输出进行需求调整,很多时候…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...

push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

云原生时代的系统设计:架构转型的战略支点
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、云原生的崛起:技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深,传统的 I…...