斐波那契数列数列/兔子数列

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
https://leetcode-cn.com/problems/climbing-stairs/

方法

斐波那契数列有一个特征就是 这个数列从第3项开始，每一项都等于前两项之和。 最简单的解法就是递归😂,but，n超过50就很慢了，100标签页直接卡死。

递归

function climbStairs(n) {
    return n < 3 ? n : climbStairs(n-1) + climbStairs(n-2)
};
console.log(climbStairs(10))

动态规划(O(n))：

function climbStairs(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
      // n=1 return 1
      // n=2 return 2
      // n=3 return 3
      // n=4 return 5
      //从第二个开始
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
console.log(climbStairs(10))