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

【LeetCode刷题笔记】动态规划 — 70.爬楼梯

创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步!
更多算法知识专栏:算法分析🔥
给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

在这里插入图片描述
LeetCode题解专栏:【LeetCode刷题笔记】


目录

  • 题目链接
  • 一、题目描述
  • 二、示例
  • 三、题目分析
    • dp数组的定义
    • 基础情况
    • 递推公式
  • 四、代码实现(C++)
  • 优化

题目链接

70. 爬楼梯- 力扣(LeetCode)

一、题目描述

假设你正在爬楼梯。需要n阶你才能到达楼顶。

每次你可以爬12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

二、示例

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

三、题目分析

根据题目一次1个或2个台阶,先考虑极端情况:只有一个台阶的情况和只有两个台阶的情况

  • 只有一个台阶:1种方法:爬1个台阶

  • 只有两个台阶:2种方法:爬两次1个台阶、爬一次2个台阶

在两个台阶的问题中,第一种方法包含了只有一个台阶的情况(爬两次1个台阶:即爬了一个台阶,此时只剩下一个台阶,转化为了只有一个台阶的问题)

三个台阶时,如果爬1个台阶,还剩2个台阶,转化为了2个台阶的问题;如果爬两个台阶,还剩1个台阶,转化为了1个台阶的问题

因此,三个台阶的方法等于一个台阶的方法 + 两个台阶的方法,为动态规划问题

dp数组的定义

dp[i] 爬到第i层楼梯,有dp[i]种⽅法

基础情况

第1个台阶和第2个台阶为最基础的情况,分别是1种、2种方法

dp[1] = 1;
dp[2] = 2;

递推公式

由题目分析可得:dp[i] = dp[i-1] + dp[i-2]

四、代码实现(C++)

class Solution {
public:int climbStairs(int n) {vector<int> dp(n+1);if(n == 1) return n;if(n == 2) return n;dp[1] = 1;dp[2] = 2;for(int i = 3;i <=n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

在这里插入图片描述

优化

以三个台阶为例,第三个台阶只依赖于前两个台阶的方法和,第i个台阶只依赖于i - 1i - 2的和

只需关注前两个的值,其余的可以不去考虑, vector<int> dp(n+1) 缩小为 dp[3],优化空间复杂度(在数据n较大的情况下)

class Solution {
public:int climbStairs(int n) {int dp[3];  	//dp[0]占1个if(n == 1) return n;if(n == 2) return n;dp[1] = 1;dp[2] = 2;int sum = 0;for(int i = 3;i <=n; i++){sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
};

** **


在这里插入图片描述

大家的点赞、收藏、关注将是我更新的最大动力! 欢迎留言或私信建议或问题。
大家的支持和反馈对我来说意义重大,我会继续不断努力提供有价值的内容!
如果本文哪里有错误的地方还请大家多多指出(●'◡'●)

相关文章:

【LeetCode刷题笔记】动态规划 — 70.爬楼梯

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞 关注支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; 更多算法知识专栏&#xff1a;算法分析&#x1f525; 给大家跳段街舞感谢…...

2024腾讯校招后端面试真题汇总及其解答(三)

21【算法题】反转链表 题目: 给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。 示例 1: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]示例 2: 输入:head = [1,2] 输出:[2,1]示例 3: 输入:head = [] 输出:[]提示: 链表中节点的数目范围是 [0, 5…...

mysql的分组group by

文章目录 一、介绍1、分组查询的内容2、多字段分组3、将查询内容连接group_concat4、有条件的分组查询having 一、介绍 将某个字段的相同值分为一组&#xff0c;分组查询的结果强调的是一个整体&#xff0c;每组内容只显示一行分组查询的内容一般要查询分组字段&#xff0c;因…...

Swoole 介绍以及 编译安装

Swoole是什么&#xff1f; Swoole是一个PHP语言的开源异步网络通信引擎&#xff0c;它是以PHP语言为基础&#xff0c;以C语言编写的扩展。它可以让PHP语言程序拥有异步网络通信能力&#xff0c;并且能够支持高并发、高性能的TCP/UDP/Unix Socket/HTTP服务器。 Swoole的优势 …...

Ubuntu终端指令

目录 目录 一、基本指令 1.命令行提示符 2.切换用户 3.修改密码 4.查看当前目录下的文件 5.修改文件权限---chmod 6.cd 切换路径 7.touch 8.cat 9.echo 10.mkdir 11. rm/rmdir 二、在线下载软件 1.更新软件源 2.更新软件列表 3.下载软件 三、离线安装软件 1. …...

python给json 转实体类加注释的代码实现

1 通过 GsonFormatPlus 生成的实体类 package com.zcl;import java.util.List;public class Test{/*** org_code*/private String org_code;/*** code*/private String code;/*** name*/private NameDTO name;/*** vendorextends*/private VendorextendsDTO vendorextends;/**…...

绘制三角波与梯形波

函数 使用三角函数及反三角函数 在线编辑运行工具 JupyterLite Retro - Notebook 三角波 import numpy as np import matplotlib.pyplot as plt # 创建一个从-2π到2π(包含2π)的等差数列,步长为0.01 x = np.arange(-4*np.pi, 4*np.pi, 0.01) # 计算y值 y = np.…...

【Git】 git push 提示Not possible to fast-forward,无法提交也无法提交程序

目录 一、执行rebase操作 二、取消rebase操作 错误内容 # git push To gitlab.aipark.com:aits/data-intergration.git! [rejected] zjk-prod-20230823 -> zjk-prod-20230823 (fetch first) error: failed to push some refs to gitlab.aipark.com:aits/data-in…...

优思学院|为什么质量工程师在别人看是“救火“的呢?

为什么质量工程师在别人看是‘救火’的呢&#xff1f;现今的质量管理体系已经很成熟&#xff0c;一家公司质量部门会有IQC、IPQC、OQC负责来料、过程质量、成品质量等等&#xff0c;而质量工程师&#xff08;QE&#xff09;的工作是要确保这些活动合理和有效&#xff0c;不产生…...

VMware Explore | 联想与VMware扩大合作带来生成式AI和多云解决方案

*带有 VMware Cloud 的全新联想 ThinkSystem 生成式 AI 解决方案&#xff0c;采用 NVIDIA 加速计算和软件&#xff0c;提供专为实现下一代 AI 工作负载而打造的 GPU 密集型平台。 联合创新实验室为商业中端市场和企业提供即用型混合多云解决方案。 全新 Lenovo TruScale Hybr…...

8月份徒弟企业面试后反馈的软件测试面试题(含金量高请收藏)

hello&#xff0c;我是清风。最近很多粉丝私信我要软件测试学习和面试资料&#xff0c;今天来安排一下面试题。我这里从来不缺永远不缺的就是面试提。我个人有几年软件测试面试官经验先不谈&#xff0c;我的徒弟每个月出去面试&#xff0c;我会叫他们录音。面试题都会反馈给我 …...

私有云不是真正的云计算!

大数据产业创新服务媒体 ——聚焦数据 改变商业 中国云计算遇到困境&#xff0c;IaaS层面&#xff0c;阿里云、腾讯云等增长乏力&#xff1b;SaaS没有发展起来。反观美国&#xff0c;整个云计算蓬勃发展&#xff0c;AWS、微软云、谷歌云体量更大&#xff0c;增速却不低&#x…...

netperf 测试时延和吞吐

一、Netperf是一种网络性能测试工具&#xff0c;主要基于TCP或UDP的传输。可以测量TCP和UDP传输的吞吐量、时延、CPU 占用率等性能参数。Netperf测试结果所反映的是一个系统能够以多块的速度向另一个系统发送数据&#xff0c;以及另一个系统能够以多块的速度接收数据。 二、打…...

安卓预制权限添加规则

android:protectionLevel 可以在 android/frameworks/base/core/res/AndroidManifest.xml查询 signature|preinstalled 加在 这个文件里 privapp-permissions-xx.xml dangerous 加在 default-permissions/default-mega-permissions.xml normal 不需要加 不存在两个文件都加…...

D3JS简介

D3JS 什么是D3js D3.js是一个流行的JavaScript数据可视化库&#xff0c;它提供了一系列的API和工具&#xff0c;用于创建交互式的数据图表、地图等可视化效果。以下是一些D3.js的特点和用途&#xff1a; 数据驱动&#xff1a;D3.js基于数据驱动的思想&#xff0c;将数据和视觉…...

系统架构设计师(第二版)学习笔记----系统工程

【原文链接】系统架构设计师&#xff08;第二版&#xff09;学习笔记----系统工程 文章目录 一、系统工程方法1.1 系统工程方法的特点1.2 系统工程方法种类1.3 霍尔三维结构的7个阶段1.4 霍尔三维结构的7个步骤1.5 切克兰德方法的7个步骤1.6 并行工程的目标1.7 并行工程强调以下…...

java spring cloud 企业工程管理系统源码+二次开发+定制化服务

鸿鹄工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离构建工程项目管理系统 1. 项目背景 一、随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大。为了提高工程管理效率、减轻劳动强度、提高信息处理速度和准确性&#xff0c;公司对内部工程管…...

IMX6ULL移植篇-boot 命令的学习

一. boot 命令简介 uboot 的作用是启动 Linux系统。所以 uboot 肯定有相关的 boot(引导)命令来启动 Linux。 常用的与 boot 有关的命令有&#xff1a;bootz、bootm 和 boot。 本文主要学习 boot 命令的使用。 本文接上一篇文章&#xff0c;如下&#xff1a; IMX6ULL移植篇…...

Python字典和集合操作指南:创建、获取值、修改和删除键值对,复制和遍历方法全解析

文章目录 字典&#xff08;dict&#xff09;创建字典获取字典中的值修改字典删除字典中的键值对复制字典字典推导式遍历字典使用keys()方法使用values()方法使用items()方法 小结 集合&#xff08;set&#xff09;创建集合集合操作集合运算小结 python精品专栏推荐python基础知…...

unity 接收拼接数据进行纹理替换且保存相机纹理到rtsp server(一)

1 rtsp 协议后编码解码 rtsp协议的问题就是&#xff0c;拼接完成后&#xff0c;还需要编码&#xff0c;而unity里面再需要解码&#xff0c;需要的过程多了一步编码再解码&#xff0c;大大加重了 2 rtsp 协议后轻量编码 rtsp协议使用mjpeg进行图片传输。why&#xff1f;这样做…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...