原題鏈接:? http://oj.leetcode.com/problems/climbing-stairs/ ?
這道題目是求跑樓梯的可行解法數量。每一步可以爬一格或者兩個樓梯，可以發現，遞推式是f(n)=f(n-1)+f(n-2)，也就是等于前一格的可行數量加上前兩格的可行數量。熟悉的朋友可能發現了，這個遞歸式正是 斐波那契數列 的定義，不熟悉的朋友可以看看 Wiki - 斐波那契數列 。根據這個定義，其實很容易實現，可以用遞歸或者遞推都是比較簡單的，下面列舉一下遞推的代碼：? 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; }

可以很容易判斷，上面代碼的時間復雜度是O(n)，面試一般都會實現一下，不過還沒完，面試官會接著問一下，有沒有更好的解法？還真有，斐波那契數列其實是有O(logn)的解法的。根據wiki我們知道，斐波那契數列是有通項公式的，如下：

所以如果我們用 Pow(x, n)中介紹的分治法來求解這個n次冪的話可以完成O(logn)的求解。還有另一種理解方法就是斐波那契數列的線性代數解法（參見 Wiki - 斐波那契數列），可以看到迭代是一個二乘二的簡單矩陣，數列的第n個數就是求解這個矩陣的n-2次冪，同樣用分治法就可以完成O(logn)的求解。 這是對于斐波那契數列問題的一般面試過程，先實現一下通常的O(n)的解法，然后再了解一下是否知道有O(logn)的解法，一般不要求實現，知道就行，不過其實實現也不是很難，有興趣的朋友可以練習一下哈。

總結

以上是生活随笔為你收集整理的Climbing Stairs -- LeetCode的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。