LeetCode经典面试题70，爬楼梯

题目地址

https://leetcode-cn.com/problems/climbing-stairs/

思路分析

这个是一个简单的递推题目，搞懂了其实就是一个斐波那契数列。你想的没错，就是你刚开始学编程时，那个兔子繁殖的问题

如果一开始有一对兔子，它们每月生育一对兔子，小兔在出生后一个月又开始生育且繁殖情况与最初的那对兔子一样，那么一年后有多少对兔子？

答案是，每月兔子的总数可以用以下数列表示：1，1，2，3，5，8，13，21，34，55，89，144，233…

来想一下，第n阶台阶可以从那一节上爬上来？只能是n-1和n-2啊，所以我们就能得到递推公式

f(n)=f(n-1)+f(n-2)，f(n)表示到n阶台阶的方法数，这不就是典型的斐波那契数列吗？有意思的是斐波那契数列有很多种实现方法，看我来一一道来。

第一种：递归
递归出口是当n=1时值为1，当n=2时值为2

class Solution {
    public int climbStairs(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

这种代码在LeetCode上会超时，因为递归比较耗时和耗内存。

第二种：递推
当n=1值为1，当n=2时值为2
当n>=3的递推公式是f(n)=f(n-1)+f(n-2)

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}

一般回答这种方式即可，时间复杂度为O(n)

第三种 通项公式
很多人其实并不知道有通项公式，通项公式如下

public class Solution {
    public int climbStairs(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }
}

时间复杂度为O(log(n))，pow 方法将会用去log(n) 的时间

第四种 矩阵快速幂
这种算法用了矩阵乘法的思想，因为要讲清楚还得复习一遍高数中的矩阵乘法，就不再解释了，有兴趣的可以找到相关的资料来看，面试中一般用递推答出来就行。

时间复杂度为 $O(log_2n)$

推荐

转载：https://blog.csdn.net/zzti_erlie/article/details/100591969