学步园

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个台阶的楼梯的走法等于：

ways(n) = ways(n-1) + ways(n-2)

恰好是Fibonacci数列。另外提一下，对Fibonacci数列的一个计算方法是，利用矩阵A=

/     \
| 1 1 |
| 1 0 |
\     /

的N次方来完成。而矩阵的N次方是可以用分而治之O(log N)实现的。这里不用了。

题解：

class Solution {
public:
    int Fibonacci(int k)
    {
        if (k==0)
            return 0;
        int fib = 1;
        int prev1 = 0, prev2 = 1;
        for(int l = 1; l < k; ++l)
        {
            prev1 = prev2;
            prev2 = fib;
            fib = prev1 + prev2;
        }
        return fib;
    }

    int climbStairs(int n) {
        return Fibonacci(n);
    }
};