leetcode-70-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

分析

这道题是利用了递归的一道问题，如果单纯的使用递归进行求解就会时间超限。因此必须用其他的方法求解。
在CPP中可以用vector动态的开辟数组，是一个比较好用的模板，用其解题可事半功倍。

第一种，递归

int climbStairs(int n) {
//    第一种解法递归
     if (n==1)
        return 1;
    else if(n==2)
        return 2;
    else
        return climbStairs(n-1)+climbStairs(n-2);
}

第二种，vector方法

int climbStairs(int n) {
    //    第二种解法
    vector<int> res(n+1);
    res[0]=1;
    res[1]=1;
    for(int i=2;i<=n;i++)
    {
        res[i]=res[i-1]+res[i-2];
    }
    return res[n];
}

注意要使用using namespace std 和#include< vector >