前兩天做算法題送悔，看到一道有意思的題目，由于看到的時候已經(jīng)快晚上11點了爪模，而我們學(xué)校是晚上11點斷電熄燈睡覺欠啤。我就記下了題目，然后就躺在床上想這個題該怎么解屋灌。
題目長這樣：
假設(shè)你正在爬樓梯洁段，需要n步你才能到達(dá)頂部。但每次你只能爬一步或者兩步共郭，你能有多少種不同的方法爬到樓頂部祠丝？比如n=3，1+1+1=1+2=2+1=3除嘹，共有3中不同的方法写半。
最開始的思路是可能跟排列組合有關(guān)，想了一會兒尉咕，發(fā)現(xiàn)思路不對啊叠蝇。又換換思路，心想年缎，可能跟前一項有關(guān)悔捶，當(dāng)我試到n=5的時候，發(fā)現(xiàn)規(guī)律了单芜！n級階梯的走法數(shù)就等于前兩項的走法數(shù)的和蜕该。跟斐波那契數(shù)列的公式有點像。唯一的區(qū)別就是最開始的兩項的值不一樣洲鸠。
第二天早上第一節(jié)正好沒課蛇损，袖子卷起來，打算把昨天的那道題實現(xiàn)了，總共幾行代碼淤齐，
private long an;
public long climbStairs(int n) {
// write your code here
if(n==0) return 1;
int rst[]={1,2};
if(n<3) return rst[n-1];
n=climbStairs(n-1)+climbStairs(n-2);
return an;
}
點擊提交，好家伙袜匿，結(jié)果網(wǎng)站提示“時間超出了限制”更啄。
原因就是使用了遞歸，我們都知道遞歸就是調(diào)用自身居灯，既然是調(diào)用函數(shù)祭务，就會有調(diào)用函數(shù)的開銷，在一個函數(shù)調(diào)用之前需要做許多工作怪嫌，比如準(zhǔn)備函數(shù)內(nèi)局部變量使用的空間义锥、搞定函數(shù)的參數(shù)等等，而且使用遞歸調(diào)用有時會產(chǎn)生棧區(qū)溢出的異常岩灭，就是因為方法調(diào)用的深度太深了拌倍，存不下了。
怎么辦呢噪径？我之前看過《劍指offer》這本書柱恤，還被我從圖書館借出來了。它里面就提到過怎么不用遞歸實現(xiàn)斐波那契數(shù)列找爱。思想是通過移動兩個“指針”實現(xiàn)從前往后算而不是遞歸那樣從后往前算梗顺。我們來看看修改之后的代碼：
private long an;
public long climbStairs(int n) {
// write your code here
if(n==0) return 1;
int rst[]={1,2};
if(n<3) return rst[n-1];
long a1=1,a2=2;
for(int i=3;i<=n;i++){
an=a1+a2;
a1=a2;//每次都往后移動這兩個“指針”
a2=an;
}
return an;
}
更多文章，歡迎訪問個人博客我的博客
