070.爬楼梯

作者：沉默王二
发布时间：2023-01-10T11:23:06.364+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

070.爬楼梯

题意

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

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

难度

简单

示例

示例 1：

输入：n = 2

解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

示例2：

输入：n = 3

解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

分析

我们先写出比较小的情况下的答案：

• 当时候
• ans=1
• 当时候
• ans=1
• 当时候
• ans=2
• 当时候
• ans=3
• 当时候
• ans=5

我们可以发现一个规律——时的ans等于和的ans之和。

想要证明这个结论也非常简单，因为我们每次只能爬 1 个或 2 个台阶，那么当前台阶，只能从之前的 1 个台阶或者 2 个台阶爬过来，所以答案就是它们二者之和，即。

这样子，我们就可以在的时间内，计算出答案了。

class Solution {

        int[] f = new int[]{1,1,2};        for(int i = 2;i <= n;i++){            f[i % 3] = f[(i - 1 + 3) % 3] + f[(i - 2 + 3) % 3];        }        return f[n % 3];    }}

执行效率：

这其实是典型的递推问题，也是著名的斐波那契数列衍生出来的问题，同时是最基础的动态规划问题。

总结

本题不算难，更多的是作为递推和动态规划的引入，方便初学者学习。

力扣链接：https://leetcode.cn/problems/climbing-stairs/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1300 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

070.爬楼梯

题意

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

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

难度

简单

示例

示例 1：

输入：n = 2

解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

示例2：

输入：n = 3

解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

分析

我们先写出比较小的情况下的答案：

• 当时候
• ans=1
• 当时候
• ans=1
• 当时候
• ans=2
• 当时候
• ans=3
• 当时候
• ans=5

我们可以发现一个规律——时的ans等于和的ans之和。

想要证明这个结论也非常简单，因为我们每次只能爬 1 个或 2 个台阶，那么当前台阶，只能从之前的 1 个台阶或者 2 个台阶爬过来，所以答案就是它们二者之和，即。

这样子，我们就可以在的时间内，计算出答案了。

class Solution {

        int[] f = new int[]{1,1,2};        for(int i = 2;i <= n;i++){            f[i % 3] = f[(i - 1 + 3) % 3] + f[(i - 2 + 3) % 3];        }        return f[n % 3];    }}

执行效率：

这其实是典型的递推问题，也是著名的斐波那契数列衍生出来的问题，同时是最基础的动态规划问题。

总结

本题不算难，更多的是作为递推和动态规划的引入，方便初学者学习。

力扣链接：https://leetcode.cn/problems/climbing-stairs/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1300 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

070.爬楼梯

题意

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

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

难度

简单

示例

示例 1：

输入：n = 2

解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

示例2：

输入：n = 3

解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

分析

我们先写出比较小的情况下的答案：

• 当时候
• ans=1
• 当时候
• ans=1
• 当时候
• ans=2
• 当时候
• ans=3
• 当时候
• ans=5

我们可以发现一个规律——时的ans等于和的ans之和。

想要证明这个结论也非常简单，因为我们每次只能爬 1 个或 2 个台阶，那么当前台阶，只能从之前的 1 个台阶或者 2 个台阶爬过来，所以答案就是它们二者之和，即。

这样子，我们就可以在的时间内，计算出答案了。

class Solution {

        int[] f = new int[]{1,1,2};        for(int i = 2;i <= n;i++){            f[i % 3] = f[(i - 1 + 3) % 3] + f[(i - 2 + 3) % 3];        }        return f[n % 3];    }}

执行效率：

这其实是典型的递推问题，也是著名的斐波那契数列衍生出来的问题，同时是最基础的动态规划问题。

总结

本题不算难，更多的是作为递推和动态规划的引入，方便初学者学习。

力扣链接：https://leetcode.cn/problems/climbing-stairs/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1300 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412