算法-爬楼梯

随缘刷，不计时

题目

爬楼梯，每次只能爬一阶或两阶，问 n 阶楼梯有多少种爬法？

例： 2 阶

解： 1 + 1; 2. 两种

例：3 阶

解：1 + 1 + 1； 2 + 1； 1 + 2. 三种

原题传送门

思考

从这题开始，刷 dp！

动态规划一般用于大问题拆解成小问题求解，例如极值等等(好像基本都是极值)

这题同理可以将问题拆解下，找出通用公式

1 阶： 1 种
2 阶： 2 种 | 1 + 1； 2
3 阶： 3 种 | 1 + 1 + 1； 2 + 1； 1 + 2
4 阶： 5 种 | 1+1+1+1；1+2+1；2+1+1；2+2
...

可以看到 第 n 阶的话，应该是 n - 1 和 n - 2 的解法之和(类似斐波那契)

得出此解

function climb (n) {
  const dp = Array.from({ length: n })

  for(let i = 0; i < n; i++) {
    if (i == 0 || i == 1) {
      dp[i] = i + 1
    } else {
      dp[i] = dp[i - 1] + dp[i - 2]
    }
  }

  return dp[n - 1]
}

这和斐波那契一样 作为动态规划思想的入门是可以的