02_爬楼梯

简介: 02_爬楼梯

70. 爬楼梯

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

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

注意:给定 n 是一个正整数。

示例 1:

  • 输入: 2
  • 输出: 2
  • 解释: 有两种方法可以爬到楼顶。
  • 1 阶 + 1 阶
  • 2 阶

示例 2:

  • 输入: 3
  • 输出: 3
  • 解释: 有三种方法可以爬到楼顶。
  • 1 阶 + 1 阶 + 1 阶
  • 1 阶 + 2 阶
  • 2 阶 + 1 阶

【思路】

动态五部曲

定义一个一维数组来记录不同楼层的状态

1、确定dp数组及其下标的含义:

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

2、确定递推公式

如何可以推出dp[i]呢?

从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来。

首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推导dp[i]的时候,一定要时刻想着dp[i]的定义,否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性!

3、dp数组如何初始化

再回顾一下dp[i]的定义:爬到第i层楼梯,有dp[i]种方法。

那么i为0,dp[i]应该是多少呢,这个可以有很多解释,但基本都是直接奔着答案去解释的。

例如强行安慰自己爬到第0层,也有一种方法,什么都不做也就是一种方法即:dp[0] = 1,相当于直接站在楼顶。

但总有点牵强的成分。

那还这么理解呢:我就认为跑到第0层,方法就是0啊,一步只能走一个台阶或者两个台阶,然而楼层是0,直接站楼顶上了,就是不用方法,dp[0]就应该是0.

其实这么争论下去没有意义,大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过,然后就往结果上靠去解释dp[0] = 1。

从dp数组定义的角度上来说,dp[0] = 0 也能说得通。

需要注意的是:题目中说了n是一个正整数,题目根本就没说n有为0的情况。

所以本题其实就不应该讨论dp[0]的初始化!

我相信dp[1] = 1,dp[2] = 2,这个初始化大家应该都没有争议的。

所以我的原则是:不考虑dp[0]如何初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推,这样才符合dp[i]的定义。

4、确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的

5、举例推导dp数组

// 常规方式
public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 用变量记录代替数组
class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int a = 1, b = 2, sum = 0;
        for(int i = 3; i <= n; i++){
            sum = a + b;  // f(i - 1) + f(i - 2)
            a = b;        // 记录f(i - 1),即下一轮的f(i - 2)
            b = sum;      // 记录f(i),即下一轮的f(i - 1)
        }
        return b;
    }
}
相关文章
|
安全 数据挖掘 Linux
Linux命令rpm深度解析
`rpm`是Linux下的软件包管理器,用于安装、升级、卸载和查询`.rpm`包,常见于Red Hat系Linux。它管理依赖、维护软件信息数据库,支持版本控制和安全验证。常用命令如`-i`安装,`-U`升级,`-e`卸载,`-q`查询。安装时用`-v`和`-h`可查看详细信息和进度。注意依赖关系、权限和签名验证,最佳实践包括使用仓库、定期更新和备份数据。
|
7月前
|
存储 人工智能 自然语言处理
《打造高准确率QClaw知识库:从清洗到拆分的完整实操流程》
本文针对QClaw本地知识库导入后普遍存在的答非所问、信息编造问题,打破“一键上传即可”的普遍误区,基于上百份不同类型文档的三周实测对比,揭示决定知识库效果的核心逻辑并非上传动作本身。系统讲解从文档清洗、语义单元拆分、重叠窗口设置、元数据标注到导入后验证优化的完整实操流程,纠正了按固定字数拆分、盲目追求文档数量等常见错误,给出大文件、结构化数据的特殊处理方案,帮助用户零失败打造高准确率的个人专属知识库。
491 1
|
5月前
|
人工智能 JSON 自然语言处理
GEO内容工程:从买家问题到AI答案
GEO(生成式引擎优化)不是简单写文章,而是构建可持续的内容工程体系:从客户真实问题出发,结构化企业知识与信任证据,通过原子化内容、模板化生产、自动化校验和数据反馈闭环,让外贸B2B企业能力被AI准确理解、引用并转化。
476 0
|
9月前
|
人工智能 自然语言处理 JavaScript
一分钟部署OpenClaw(Clawdbot)+问题解答,最爽的一键启动!
OpenClaw(前身为 Clawdbot、Moltbot)是一款开源 AI 代理与自动化平台,具备自然语言控制、任务自动化执行、多模型兼容等核心能力,可实现文件处理、邮件管理、日程规划、多工具协同等多样化功能,堪称 “专属数字员工”。2026 年阿里云推出的轻量应用服务器一键部署方案,通过预置专属镜像简化了复杂的环境配置流程,无需专业技术储备,零基础用户也能快速完成部署,实现 7×24 小时不间断运行。本文将详细拆解部署全流程,并针对性解读常见问题与解决方案,全程无营销表述,严格遵循技术文档核心逻辑。
1529 4
|
Windows
显示器设置
显示器设置
705 2
|
人工智能 小程序 Android开发
鸿蒙应用开发从入门到入行 - 篇1:HarmonyOS介绍——带你深入理解鸿蒙特性
本文介绍了华为的HarmonyOS(鸿蒙系统),这是一个面向全场景的分布式操作系统,不仅适用于手机和平板,还支持电脑、车机、手表、电视等多种设备。文章详细解析了鸿蒙系统的三大特性:一次开发多端部署、可分可合自由流转、统一生态原生智能,并分析了鸿蒙系统为何能蚕食安卓市场份额的原因。猫林老师认为,鸿蒙凭借其先进的技术和国内政策支持,有望在未来的市场中占据重要地位。最后,文章提供了学习鸿蒙系统的建议和一些课后练习,帮助读者更好地理解和掌握这一系统。
2161 7
鸿蒙应用开发从入门到入行 - 篇1:HarmonyOS介绍——带你深入理解鸿蒙特性
|
前端开发 Java 开发者
【springboot】中使用--WebMvcConfigurer
通过实现 `WebMvcConfigurer` 接口,Spring Boot 开发者可以灵活地自定义和扩展 Spring MVC 的配置。无论是视图解析、拦截器、跨域请求处理,还是静态资源和消息转换器配置,`WebMvcConfigurer` 都提供了一致的接口来实现这些功能。掌握这些配置方法,可以使开发者在 Spring Boot 项目中更加游刃有余地进行各种定制化需求的开发。
1084 14
|
机器学习/深度学习 人工智能 自然语言处理
|
NoSQL Redis
RedisTemplate.opsForSet()用法简介并举例
RedisTemplate.opsForSet()用法简介并举例
1987 2