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?

分析：

最简单的动态规划，只要带入几个例子，确定开始没问题就好。这题目用个vector(n + 1)，这样能把0个台阶的情况也考虑进来。

解法：

class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer
     */
    int climbStairs(int n) {
        // write your code here
        if (n == 0) {
            return 1;
        }

        vector<int> results(n + 1, 0);
        results[0] = 1;
        results[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            results[i] = results[i - 1] + results[i - 2];
        }
        return results[n];
    }
};