Leetcode_70_Climbing Stairs

[lihe]

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?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

算法思路：

1. 设置递推数组dp[0...n], dp[i]，dp[i]代表到达第i阶有多少种走法，初始化为0；
2. 设置dp[1] = 1，dp[2] = 2;
3. 利用dp[i] = dp[i - 1] + dp[i - 2]从第三阶推至第n阶。

class Solution {
public:
    int climbStairs(int n) {
    	std::vector<int> dp(n + 3, 0);
    	dp[1] = 1;
    	dp[2] = 2;
    	for (int i = 3; i <= n; i++){
	    	dp[i] = dp[i-1] + dp[i-2];
	    }
	    return dp[n];
    }
};