LeetCode題解：Climbing Stairs

題目連結：

Climbing Stairs

題目描述：

You are climbing a stair case. It takes n steps to reach to the top。

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

題目解釋:

假設你正在怕一個樓梯，你要走n步才能到達樓梯頂部，每一次你既可以爬一個台階，也可以爬兩個台階，那麼一共有多少種不同的方式可以走到樓梯的頂部？

解題方案：

由題目描述，我們可以知道，數字n代表着台階的階數，這個就是我們的輸入。然後我們根據輸入推斷出一共有多少不同的方案，例如 n = 0,那麼我的方案為s = 0, n = 1 , s = 1, n = 2, s = 2, n = 3 , s = 3………; 到走到最後一步時，我們既可以從第n-1個台階跨上去，也可以從n-2個台階上跨上去，是以我們走n個台階的方案數就是n-1個台階的方案數和n-2個台階方案數之和，S[n] = S[n-1] + S[n-2]; 這是什麼？ 大聲的告訴我！ 這是不是斐波那契數列！！！？？？，

明白了解題思路我們的代碼就很好寫了：

int climbStairs(int n) 
{
    int stairs[];

    if (n <= )
    {
        return n;
    }    
    stairs[] = ;
    stairs[] = ;

    for (int i = ; i <= n; ++i)
    {
        stairs[i] = stairs[i-] + stairs[i-]; 
    }
    return stairs[n];
}
           

遇到爬樓梯問題已經四年了，一直還不知道它是斐波那契數列呢。