我是小小強(qiáng)，這是我的第12篇原創(chuàng)文章，閱讀需要大約10分鐘。

題目

LintCode:爬樓梯

描述

假設(shè)你正在爬樓梯，需要n步你才能到達(dá)頂部。但每次你只能爬一步或者兩步，你能有多少種不同的方法爬到樓頂部？

樣例

比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法

返回 3

思路

假設(shè)當(dāng)前在第n階上，那么從前面登上第n階只有兩種方式，要么從第n-1階一步登上來，要么從n-2階一步登上來。對(duì)于n-1或者n-2無法也是重復(fù)相同的步驟。所以對(duì)第n階來說，總的方法應(yīng)該是n-1階和n-2階方式之和。

先排列試試看:

登上第1級(jí)：1種
登上第2級(jí)：2種
登上第3級(jí)：1+2=3種（前一步要么從第1級(jí)邁上來,要么從第2級(jí)邁上來）
登上第4級(jí)：2+3=5種（前一步要么從第2級(jí)邁上來,要么從第3級(jí)邁上來）
登上第5級(jí)：3+5=8種
登上第6級(jí)：5+8=13種
登上第7級(jí)：8+13=21種
登上第8級(jí)：13+21=34種
登上第9級(jí)：21+34=55種
登上第10級(jí)：34+55=89種．

仔細(xì)觀察，這就是斐波納契數(shù)。

實(shí)現(xiàn)

1. java實(shí)現(xiàn)

public class Solution {
    public int climbStairs(int n) {
        int a = 0, b = 1;
        while (n > 0){
            b = a + b;
            a = b - a;
            n--;
        }
        return b;
    }
}

想法

對(duì)于有些算法題時(shí)，如果一時(shí)想不出來解題思路，不如試試從開始條件遞歸的算一下。對(duì)于本題，最開始就陷入死胡同。