## 每次爬 1 或 2 个台阶，爬上n阶有几种爬法？ #### 首先我们可以先假设有10阶，爬上第10阶有两种可能，从第8阶或者第9阶，也就是f（10） = f（9） + f（8），那么同样的，爬上第9阶也有两种可能，f（9） = f（8） + f（7），由此我们可以得出f（n） = f（n-1）+f（n-2） * 方法一：递归 采用递归是最直接的方式，但是很费时，性能不好 ``` function digui (n){ if(n <= 2){ return n }else{ return digui(n-1) + digui(n-2) } } console.log(digui(5)) ``` * 方法二：动态规划 ``` 1.0 function temp (n) { const dp = [0,1]; let temp = ''; for(let i = 0 ; i < n ; i ++){ temp = dp[0]; dp[0] = dp[1]; dp[1] = temp + dp[1]; } return dp[1] } console.log(temp(5)) 2.0 // 该方法采用的是es6的解构，同上一方法相同，只是写法不同 function temps (n){ let a = b = 1 ; for(let i = 0 ; i < n ; i ++){ [a , b] = [b , a + b] } return a } console.log(temps(5)) 3.0 var cli = function(n,map) { if(n <= 2){ return n; } if(map.get(n)){ return map.get(n) }else{ let value = cli(n-1 , map) + cli(n-2 , map); map.set(n , value); return value } } console.log(cli(5 , new Map())) 4.0 var test = function (n) { let result = new Array(n + 1); result[1] = 1 ; result[2] = 2; for(let i = 3 ; i < n + 1 ; i ++){ result[i] = result[i - 1] + result[i - 2] } return result[n] } console.log(test(5)) 5.0 function fil(n){ var arr = [1,2]; for(let i = 2 ; i < n ; i ++){ arr.push(arr[i-1] + arr[i-2]) } return arr[n-1] } console.log(fil(5)) ```