1、青蛙跳台阶
题目描述：一只青蛙一次可以跳一级台阶，也可以跳两级台阶，问：青蛙跳上n级台阶一共有多少种跳法：
分析：
我们倒着推，不管青蛙前面怎么跳，但是它最后一次跳跃只有两种情况：
1.跳两级，那么剩余台阶n-2，剩余跳法f(n-2)
2.跳一级，剩余台阶n-2，剩余跳法f(n-1)
所以有 f(n) = f(n-1) + f(n-2)
现在想想斐波那契数列，一毛一样
function numWays(n){
if(n<) {
return 1
}
if(n<=3){
return n
}
return numWays(n-1)+numWays(n-2)
}
但是这样写效率太低，
可以换个思路
function numWays(n){
if(n <= 1){
return 1
}
let dp = [1,1,2]
for(let i = 2; i <= n; i++) {
dp[i] = dp[i -1] + dp[i - 2]
}
return dp[n]
}
