爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：

给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

题解

解题思路

利用 动态规划 的思想。

• 想要爬一层，只有一种可能；
• 想要爬两层，要么一次一阶，要么一次两阶，只有两种可能；
• 想要爬三层，要么先到第一阶，一次迈两步上来，要么先到第二阶，一次迈一步上来，令上一阶需要的次数为 f(1) , 上两阶需要的次数为 f(2) ,所以上三阶可以有 f(1) + f(2) 种可能性；
• 依次类推，上n阶有 f(n - 1) + f(n - 2) 种可能性 由于这个期间存在多次重复计算，所以可以把每次计算的结果存储下来，避免重复计算，以提高性能。可得解题过程如下：

/**
 * 爬楼梯
 * @param {number} n
 * @return {number}
 */

export default function(n: number): number {
  const steps = [1, 2]
  const getRes = () => {
    if (n < 3) {
      return n
    } else {
      for (let i = 3; i <= n; i++) {
        steps.push(steps[i - 2] + steps[i - 3])
      }
      return steps[steps.length - 1]
    }
  }
  return getRes()
}