1、青蛙跳臺階
題目描述：一只青蛙一次可以跳一級臺階吁伺，也可以跳兩級臺階饮睬，問：青蛙跳上n級臺階一共有多少種跳法：
分析：
我們倒著推，不管青蛙前面怎么跳篮奄，但是它最后一次跳躍只有兩種情況：
? ? 1.跳兩級捆愁，那么剩余臺階n-2，剩余跳法f(n-2)
? ? 2.跳一級窟却，剩余臺階n-2昼丑，剩余跳法f(n-1)
所以有? ? ? f(n) = f(n-1) + f(n-2)
現(xiàn)在想想斐波那契數(shù)列夸赫，一毛一樣
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]
}
