Climbing Stairs -- LeetCode

原题链接: http://oj.leetcode.com/problems/climbing-stairs/ 
这道题目是求跑楼梯的可行解法数量。每一步能够爬一格或者两个楼梯。能够发现。递推式是f(n)=f(n-1)+f(n-2)，也就是等于前一格的可行数量加上前两格的可行数量。

熟悉的朋友可能发现了，这个递归式正是斐波那契数列的定义，不熟悉的朋友能够看看Wiki - 斐波那契数列。依据这个定义，事实上非常easy实现，能够用递归或者递推都是比較简单的，以下列举一下递推的代码： 

public int climbStairs(int n) {
    int f1 = 1;
    int f2 = 2;
    if(n==1)
        return f1;
    if(n==2)
        return f2;
    for(int i=3;i<=n;i++)
    {
        int f3 = f1+f2;
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

能够非常easy推断。上面代码的时间复杂度是O(n)，面试一般都会实现一下。只是还没完，面试官会接着问一下，有没有更好的解法？还真有，斐波那契数列事实上是有O(logn)的解法的。

依据wiki我们知道，斐波那契数列是有通项公式的，例如以下：

所以假设我们用Pow(x, n)中介绍的分治法来求解这个n次幂的话能够完毕O(logn)的求解。还有还有一种理解方法就是斐波那契数列的线性代数解法（參见Wiki - 斐波那契数列）。能够看到迭代是一个二乘二的简单矩阵。数列的第n个数就是求解这个矩阵的n-2次幂，相同用分治法就能够完毕O(logn)的求解。

这是对于斐波那契数列问题的一般面试过程，先实现一下通常的O(n)的解法，然后再了解一下是否知道有O(logn)的解法。一般不要求实现。知道即可，只是事实上实现也不是非常难。有兴趣的朋友能够练习一下哈。