假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

样例

比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法

返回 3

标签

动态规划

思路

使用动态规划，用 dp[i] 记录走到第 i 步共有多少种方法

动态转移方程为：dp[i] = dp[i-1] + dp[i-2]

比如：

登上第1级：1种

登上第2级：2种

登上第3级：1+2=3种（前一步要么从第1级迈上来,要么从第2级迈上来）

登上第4级：2+3=5种（前一步要么从第2级迈上来,要么从第3级迈上来）

登上第5级：3+5=8种

登上第6级：5+8=13种

登上第7级：8+13=21种

登上第8级：13+21=34种

登上第9级：21+34=55种

登上第10级：34+55=89种

code

class Solution {public:    /**     * @param n: An integer     * @return: An integer     */    int climbStairs(int n) {        // write your code here        if(n <= 0) {            return 1;        }        vector
    
      dp(n+1, 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];    }};