题目英文描述：
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 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

代码（动态规划）（O(n)）：

class Solution {
public:
    int climbStairs(int n) {
        int first = 0, second = 0, third = 1;
        for(int i = 1; i <= n; ++i) {
            first = second;
            second = third;
            third = first + second;
        }
        return third;
    }
};

代码（斐波那契数列通项公式）(O(logn))：

斐波那契数列通项公式

class Solution {
public:
    int climbStairs(int n) {
        double sqrt5 = sqrt(5);
        double fibn = pow((1 + sqrt5)/2, n + 1) - pow((1 - sqrt5)/2, n+1);
        return (int)(fibn / sqrt5);
    }
};