n级阶梯1步2步走问题

题目：一个长阶梯有n级，可以一次走1级，一次走2级，一共有多少种走法？

经典的动态规划问题，从结果来看：

• 到达第n层阶梯的方式只有两种，走一步然后结束，或者走两步然后结束。
• 到达第n-1层阶梯的方式只有两种，走一步然后结束，或者走两步然后结束。
• ……

抽离于动态规划模型，动态规划解题主要是解决两点（一般难题也就从这两个点来设置）

1. 动态方程
2. 边界条件

let arr = new Array(n).fill(0)

// 边界条件
arr[0] = 1
arr[1] = 2

for (let i = 2; i<arr.length; i++) {
  // 动态方程
  arr[i] = arr[i-1] + arr[i-2]
}

console.log(arr[n-1])

还可以用递归（不建议用，复杂度太高指数级，但是因为和递归看起来有点像，所以写出来作为比较）

let jie = n => {
  if(n === 1) return 1;
  if(n === 2) return 2;
  if(n > 2)  return jie(n-1) + jie(n-2);
}