题目

链接：爬楼梯

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

题解1

具体思路 思路提供：Storm https://leetcode.cn/problems/climbing-stairs/solutions/2252184/70-pa-lou-ti-by-stormsunshine-gj2k/

对于非负整数 nnn，计算到达第 nnn 个台阶的方案数 f(n)f(n)f(n) 的规则如下。

当 n≤1n \le 1n≤1 时，f(n)=1f(n) = 1f(n)=1。

当 n≥2n \ge 2n≥2 时，f(n)=f(n−1)+f(n−2)f(n) = f(n - 1) + f(n - 2)f(n)=f(n−1)+f(n−2)。

根据计算规则，直观的做法是使用递归实现计算到达第 nnn 个台阶的方案数。递归的终止条件是 n≤1n \le 1n≤1，此时返回 111。当 n≥2n \ge 2n≥2 时，使用递归计算 f(n)f(n)f(n)。

不带记忆化的递归存在重复计算，时间复杂度是指数级，该时间复杂度过高，需要优化。

使用记忆化搜索可以避免重复计算，将时间复杂度降低到线性。

记忆化搜索的边界情况是当 n≤1n \le 1n≤1 时 f(n)=1f(n) = 1f(n)=1，此时可直接返回结果。当 n≥2n \ge 2n≥2 时，f(n)=f(n−1)+f(n−2)f(n) = f(n - 1) + f(n - 2)f(n)=f(n−1)+f(n−2)，需要使用哈希表存储非边界情况的已经计算过的结果。计算得到 f(n)f(n)f(n) 即为结果。

public class Solution {
    public int ClimbStairs(int n) {
       return returnValue(n);
    }
    private int returnValue(int i){
        if(i==1) return 1;
        if(i>0&&i>1){
            return returnValue(i-1)+returnValue(i-2);
        }
        return 1;
    }
}

总结

爬楼梯的f(n)和斐波那契数列相似，所以数学一定要学好。

结尾

感谢您的阅读，如果有收获麻烦点个关注！如果有任何疑问或意见，可以评论区发表您的想法。
其他平台
公众号：【长生小殿】
B站：【月长生殿主】