LeetCode爬楼梯

LeetCode爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n
是一个正整数。
示例 1： 输入： 2 输出： 2
示例 2： 输入： 3 输出： 3

**1阶  1种
  2阶  2种
  3阶  3种
  4阶  5种
  f(n) = f(n-1)+f(n-2)
**

int climbStairs(int n){


    //递归会超时
    // if(n == 0 || n == 1 || n == 2)
    //     return n;
    // return climbStairs(n-1)+climbStairs(n-2);

    //动态规划
    if(n<3)
        return n;
    int dp[n+1];    //定义一个缓存数组保存前n阶楼梯的值
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i < n + 1; i++)  //n阶  dp[n]
    {
        dp[i] = dp[i-1]+dp[i-2];  //给数组赋值
    }
    return dp[n];
}