Leetcode 70.爬楼梯

简介: Leetcode 70.爬楼梯

@TOC

1 题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数
示例1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
 1.  1 阶 + 12.  2
AI 代码解读

示例2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
 1.  1 阶 + 1 阶 + 12.  1 阶 + 23.  2 阶 + 1
AI 代码解读

2 思路

动态规划 O(n)
状态表示:
f[i] 表示爬到第i个台阶的方法数,那么f[n]就代表爬到楼顶的方法数。
状态计算
因为每一次爬楼梯都有两种选择,一种是爬1阶,一种是爬两阶,所以到第i个台阶有两种方案:

  • 由第==i-1==个台阶走到第==i==个台阶。
  • 由第==i-2==个台阶走到第==i==个台阶。

边界
到第==一==个台阶只能有一种方案,即爬==一阶==。
到第==二==个台阶有两种方案,既==一次爬两阶==,或者是==爬两次一阶==。

递归
递归思路
当走到第n阶台阶时,不知道有多少种方法,可以往前退,去找第==n-1==个台阶的方法数和第==n-2==个台阶的方法数之和即为第==n==阶台阶的方法数。
终止条件

  • ==n=1==时返回==1==
  • ==n=2==时返回==2==

BUT
仅仅使用这种递归的话不出意外肯定要==超时==,因为每次计算一次n的方案数都要从n一直循环找到1或2才停止,造成时间上以及空间上都是极大的浪费。所以我们可以怎么做才能不超时且时间复杂度为 O(n) 呢?
答案是使用==记忆化搜索==。
在这里插入图片描述
记忆化搜索 O(n)
记忆化搜索的思想是,在搜索过程中,会有很多重复计算,如果我们能记录一些状态的答案,就可以减少重复搜索量。

  1. 首先使用一个表来记录已经存储下的搜索结果,一般用hash表来实现。
  2. 在每一状态搜索的开始,高效的使用hash表来检验这个状态是否出现过,如果已经出现过,直接调用答案,然后进行回溯。如果没有,则继续搜索。

在这里插入图片描述

小提示
记忆化搜索时类似于动态规划的,不同的时,它是倒做的“==递归式动态规划=="。

3 代码

动态规划

class Solution
{
public:
    int climbStairs(int n)
    {
        int dp[1000];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};
AI 代码解读

记忆化搜索

class Solution {
public:
    int f[50];
    int climbStairs(int n) {
       if (f[n])
            return f[n];
        else
        {
            if (n == 1)
                return 1;
            else if (n == 2)
                return 2;
            else
                return f[n] = climbStairs(n - 1) + climbStairs(n - 2);
        }
        
    }
};
AI 代码解读

原题链接 70. 爬楼梯

相关文章
c++类和对象一静态成员的讲解
c++类和对象一静态成员的讲解
77 0
c++类和对象一静态成员的讲解
动态切面
`AdviceConfiguration` 类用于动态注册一个基于 AspectJ 的切面顾问,该顾问通过 `@ConditionalOnExpression` 注解控制是否生效。配置中包含一个从 Apollo 获取的 JSON 值,用于构建方法拦截器的切入点表达式,涉及特定包和类。拦截器 `ControllerAdvice` 实现了 `MethodInterceptor`,用于记录请求日志,包括 URL、参数和执行时间,同时根据配置决定是否对返回结果进行加密。
金润数科JR-CLT-003-通过VIN码查询车型信息接口文档
接口名称 通过VIN码查询车型信息 接口编号 JR-CLT-003 接口描述 通过VIN码查询车型信息 接口地址 /dmp/api 请求方式 POST 加密方式 RSA2
Zookeeper应用之——队列(Queue)
Zookeeper应用之——队列(Queue) 为了在Zookeeper中实现分布式队列,首先需要设计一个znode来存放数据,这个节点叫做队列节点,我们的例子中这个节点是/zookeeper/queue。
1664 0
PaperWeekly 第52期 | 更别致的词向量模型:Simpler GloVe - Part 1
如果问我哪个是最方便、最好用的词向量模型,我觉得应该是 word2vec,但如果问我哪个是最漂亮的词向量模型,我不知道,我觉得各个模型总有一些不足的地方。且不说试验效果好不好(这不过是评测指标的问题),就单看理论也没有一个模型称得上漂亮的。
2573 0
kde
|
4天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
2767 7
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
522 0
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
759 7
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
本文详细介绍了Maven的项目管理工具特性、安装步骤和配置方法。主要内容包括: Maven概述:解释Maven作为基于POM的构建工具,具备依赖管理、构建生命周期和仓库管理等功能。 安装步骤: 从官网下载最新版本 解压到指定目录 创建本地仓库文件夹 关键配置: 修改settings.xml文件 配置阿里云和清华大学镜像仓库以加速依赖下载 设置本地仓库路径 附加说明:包含详细的配置示例和截图指导,适用于各种操作系统环境。 本文提供了完整的Maven安装和配置
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问