題目鏈接
中文版題目鏈接

昨夜走在校園的小路上，靈感乍現(xiàn)，突然明白了為什么剛好是斐波那契數(shù)列可解此題。

普通思維：
走第一步時(shí)有兩種情況，走一個(gè)臺(tái)階，或兩個(gè)臺(tái)階；

走第二步時(shí)，第一步時(shí)的兩種情況中又分別有兩種情況；
如此遞歸......

最多走n步即可，所有情況為2^n次；
然后找出少于或等于n步時(shí)經(jīng)過(guò)臺(tái)階數(shù)也剛好為n個(gè)的數(shù)量即為所求。
（為什么走n步即可？考慮到每步都只走一個(gè)臺(tái)階情況！）
代碼如下：

int N; int Num; void recursion(int count, int step) {//count記錄走過(guò)臺(tái)階個(gè)數(shù)，step為步數(shù)//printf("%d %d\n", count, step);if (step > N || count > N) {return;} else if (count == N) {Num++;return;}recursion(count+1, step+1);//一步一個(gè)臺(tái)階recursion(count+2, step+1);//一步兩個(gè)臺(tái)階 }int climbStairs(int n) {N = n;Num = 0;recursion(0, 0);return Num; } 結(jié)果：
超時(shí)！n為35時(shí)，就有點(diǎn)力不從心了。

逆向思維：
假設(shè)有20個(gè)臺(tái)階，即n=20；
則可以發(fā)現(xiàn)到達(dá)第20階有兩種情況19 + 1與18 + 2；
設(shè)到第n個(gè)臺(tái)階方法有f(n)種，則：
f(20) = f(19) + f(18);
f(19) = f(18) + f(17);
f(18) = f(17) + f(16);
如此循環(huán)......
f(3)=f(2)+f(1);
f(2)=f(1)+f(0);
f(1)=1

f(0)=1
其實(shí)到此已不難發(fā)現(xiàn)剛好是斐波那契數(shù)列，但為什么一定要用斐波那契數(shù)列？

此時(shí)又可使用遞歸

遞歸代碼如下：

int f0 = 1; int f1 = 1; int climbStairs(int n) {int count = 0;if (n == 1 || n == 0) {return 1;}count = climbStairs(n-1) + climbStairs(n-2);return count; } 結(jié)果：
性能貌似提升了一倍，但依舊超時(shí)！

問(wèn)題所在：不難發(fā)現(xiàn)，使用此種遞歸的話，會(huì)出現(xiàn)很多重復(fù)計(jì)算的地方；
比如f(20) = f(19) + f(18) 與 f(19) = f(18) + f(17)
就重復(fù)計(jì)算了f(18)，那么找到問(wèn)題所在，就好解決了；
我們只需在計(jì)算之后記錄f(18)，下次再遇到需要f(18)之處就無(wú)需計(jì)算，直接使用即可！
考慮到答案在int范圍之類，n最大取值貌似就是45了，故可以開(kāi)數(shù)組空間記錄f(1)~f(n-1);

以下代碼沒(méi)有開(kāi)數(shù)組存。
代碼如下
int climbStairs(int n) {int f0 = 1, f1 = 1, f2 = 1;for (int i = 2; i <= n; i++) {f2 = f0 + f1;f0 = f1;f1 = f2;}return f2; } 結(jié)果：
性能上有很大提升，圖為n=44；

總結(jié)

以上是生活随笔為你收集整理的leetcode之Climbing Stairs爬楼梯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。