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?           

        一開始看到這道題目的時候，不知道大家會想到什麼，我第一想法就是 斐波那契數列，不知道是不是之前看過類似的東西，第一反應就出來了。然後就是驗證看是不是。由題意知道f(1) = 1 ， f(2) = 2 ，假設n等于3，可以驗證 f(3) = f(2) + f(1)，當n=k時，f(k) 等于 f(k-1) 再爬一步，加上 f(k-2) 處爬兩步得到，即 f(k) = f(k-1) + f(k-2)，這明顯就是一個斐波那契數列，問題就變成求第n個斐波那契數列的問題啦，當然啦，求數列可以用遞歸也可以用非遞歸，為了防止n很大時遞歸速度很慢而且調用的棧空間比較大，我這裡用的是非遞歸。

        由于程式非常簡單，就直接上代碼了，如下：

class Solution {
public:
    int climbStairs(int n) {
        if(0 >= n)
        {
            return 0;
        }
        else if(1 == n)
        {
            return 1;
        }
        
        int a1 = 1;
        int a2 = 2;
        int a3 = 2;
        
        for(int i = 2; i < n; i++)
        {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }
};