LeetCode刷题-爬楼梯

前言说明

算法学习，日常刷题记录。

题目连接

爬楼梯

题目内容

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

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

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

示例1:

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶

2. 2 阶

示例2:

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 2 阶

3. 2 阶 + 1 阶

分析过程

先用最直观的归纳法找出前5项的答案，再通过比较寻找规律。

输入： 1

输出： 1

解释： 有一种方法可以爬到楼顶。

1. 1 阶

输入： 4

输出： 4

解释： 有五种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 1 阶 + 2 阶

3. 1 阶 + 2 阶 + 1 阶

4. 2 阶 + 1 阶 + 1 阶

5. 2 阶 + 2 阶

输入： 5

输出： 8

解释： 有八种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶

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

3. 1 阶 + 1 阶 + 2 阶 + 1 阶

4. 1 阶 + 2 阶 + 1 阶 + 1 阶

5. 1 阶 + 2 阶 + 2 阶

6. 2 阶 + 1 阶 + 1 阶 + 1 阶

7. 2 阶 + 1 阶 + 2 阶

8. 2 阶 + 2 阶 + 1 阶

加上示例中的输入2、3，可以得到前5个的结果如下：

输入：1、2、3、4、5

输出：1、2、3、5、8

通过比较输入1、2、3、4、5的结果可以发现，其实就是斐波那契数列，f(n) = f(n-1) + f(n-2)。

所以代码如下：

class Solution {
    public int climbStairs(int n) {
        // 直接调用递归方法
        return fibonacci(n);
    }

    // 递归法
    private static int fibonacci(int n) {
        if (n == 1 || n == 2) {
            return n;
        }

        // f(n)等于前两个相加
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

但是运行结果如下：

运行结果

运行提示超时了，当输入n = 45时，运行超时。

因为递归是很耗费时间的，所以这里不能用递归法。

我们可以选择使用迭代法，逐个叠加算出下一个结果。

从1开始往后循环叠加，每次把上一次的结果累加，上一次的结果更新为当前结果，每次加1阶，阶数记为m。

如果阶数m大于等于输入的阶数n，那么结束循环，返回当前结果。

解答代码

所以使用迭代法的代码，如下：

class Solution {
    public int climbStairs(int n) {
        // 通过比较1、2、3、4、5的结果就能发现，其实就是斐波那契数列，f(n)=f(n-1)+f(n-2)
        // n阶：1、2、3、4、5
        // 方法：1、2、3、5、8
        // 但是直接用递归法解，会超时，当n=45时就已经超时了
        // 下面从1开始递增，每次计算出当前结果，当等于n时就结束
        // 注意：n=45时，返回的结果已经到了边界值，n=46时，返回的结果已经溢出

        // 保存当前结果
        int currentTotal = 1;
        // 保存上一个结果
        int lastTotal = 1;

        int m = 1;

        // 从1开始递增
        while (m < n) {
            int temp = currentTotal;
            currentTotal += lastTotal;
            lastTotal = temp;
            ++m;
        }

        return currentTotal;
    }
}

提交结果

执行用时0ms，时间击败100.00%的用户，内存消耗35.2MB，空间击败39.10%的用户。

运行结果

原文链接

原文链接：爬楼梯