70.爬楼梯

LeetCode LeetCode 热题100 动态规划数学记忆化搜索

发布时间 : 2000-01-10 00:07

字数:989 阅读 :

评论:

70.爬楼梯

70.爬楼梯

70.1 题目

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

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

示例 1：

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

1 阶 + 1 阶
2 阶

示例 2：

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

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

提示：

1 <= n <= 45

70.2 题解

方法一：找规律（动态规划）

思路

爬到第 n 阶的方法数等于爬到第 n-1 阶和第 n-2 阶的方法数之和。因为每次只能爬1或2阶，所以第 n 阶只能从 n-1 或 n-2 到达。这就是斐波那契数列的递推关系：f(n) = f(n-1) + f(n-2)。使用两个变量滚动更新，避免数组开销。

核心思想：斐波那契数列递推，滚动变量优化空间。

具体步骤：

如果 n <= 2：返回 n。
初始化 first = 1, second = 2。
从 i = 3 到 n：
- current = first + second
- first = second, second = current
返回 second。

举例：对于 n = 3：

first=1, second=2
i=3：current=1+2=3，first=2, second=3
返回 3

复杂度分析

时间复杂度：O(n)，遍历一次。
空间复杂度：O(1)，只使用常数额外空间。

代码

// 方法一：找规律
// 爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。
static int ClimbStairs1(int n)
{
    // base case: 如果楼梯数量为 1 或 2，直接返回对应的方法数
    if (n <= 2)
    {
        return n;
    }

    // 初始化前两个台阶的方法数
    int first = 1; // 到达第一个台阶的方法数
    int second = 2; // 到达第二个台阶的方法数

    // 从第三个台阶开始计算到达每个台阶的方法数
    for (int i = 3; i <= n; i++)
    {
        // 计算当前台阶的方法数，即前两个台阶的方法数之和
        int current = first + second;

        // 更新前两个台阶的方法数，为下一次循环做准备
        first = second;
        second = current;
    }

    // 返回到达第n个台阶的方法数
    return second;
}

70.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 假设你正在爬楼梯。需要 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 阶

        #endregion

        #region 测试

        // 示例 1
        int n1 = 2;
        int result1 = ClimbStairs1(n1);
        Console.WriteLine($"示例1 输出：{result1}");

        // 示例 2
        int n2 = 3;
        int result2 = ClimbStairs1(n2);
        Console.WriteLine($"示例2 输出：{result2}");

        #endregion
    }

    #region 答案

    // 方法一：找规律
    // 爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。
    static int ClimbStairs1(int n)
    {
        // base case: 如果楼梯数量为 1 或 2，直接返回对应的方法数
        if (n <= 2)
        {
            return n;
        }

        // 初始化前两个台阶的方法数
        int first = 1; // 到达第一个台阶的方法数
        int second = 2; // 到达第二个台阶的方法数

        // 从第三个台阶开始计算到达每个台阶的方法数
        for (int i = 3; i <= n; i++)
        {
            // 计算当前台阶的方法数，即前两个台阶的方法数之和
            int current = first + second;

            // 更新前两个台阶的方法数，为下一次循环做准备
            first = second;
            second = current;
        }

        // 返回到达第n个台阶的方法数
        return second;
    }

    
    #endregion
}

70.4 运行结果

示例1 输出：2
示例2 输出：3

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com