leetcode70.md

70. 爬楼梯

描述

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：

• 给定 n 是一个正整数

实例

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

思路

1、定义子问题：F(n) = F(n-1) + F(n-2)
2、反复执行：从2循环到n，执行1

实现

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n < 2) return 1;

  const dpArr = [1, 1];
  for (let i = 2; i <= n; i++) {
    dpArr[i] = dpArr[i - 1] + dpArr[i - 2];
  }
  return dpArr[n];
};

实现-复杂度分析
时间复杂度：O(n)，因为有个 for 循环
空间复杂度：O(n)，因为创建了一个数组 dpArr

官方

var climbStairs = function (n) {
  let p = 0,
    q = 0,
    r = 1;
  for (let i = 1; i <= n; ++i) {
    p = q;
    q = r;
    r = p + q;
  }
  return r;
};

官方-复杂度分析
时间复杂度：O(n)，循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
空间复杂度：O(1)，这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。