21 - 爬楼梯

题目

假设你正在爬楼梯。需要 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 阶

解答

参考：

作者：LeetCode

链接：https://leetcode-cn.com/problems/two-sum/solution/pa-lou-ti-by-leetcode/

递归

var climbStairs = function(n) {
  const climb = function(i, n) {
    if (i > n) {
      return 0;
    } else if (i === n) {
      return 1;
    } else {
      return climb(i + 1, n) + climb(i + 2, n);
    }
  };
  return climb(0, n);
};

虽然似乎可以，但算到44的时候，就超出时间了。。毕竟时间复杂度是$O(2^n)$

反向递归

每个数到它那里只有两种可能，i-1前进一步，或i-2前进两步。那就可以存一个数组，每个元素放着每一格的所有可能的情况，就可以从最后一个倒退出所有的可能值。

var climbStairs = function(n) {
  if (n === 1) {
    return 1;
  }
  let dp = [0, 1, 2];
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

Runtime: 48 ms, faster than 91.88% of JavaScript online submissions for Climbing Stairs.

Memory Usage: 33.8 MB, less than 72.54% of JavaScript online submissions for Climbing Stairs.

其实这就是斐波那契数列。所以也可以加着做：

var climbStairs = function(n) {
  if (n === 1) {
    return 1;
  }
  let first = 1;
  let second = 2;
  for (let i = 3; i <= n; i++) {
    let sum = first + second;
    first = second;
    second = sum;
  }
  return second;
};

Runtime: 48 ms, faster than 91.88% of JavaScript online submissions for Climbing Stairs.

Memory Usage: 33.8 MB, less than 48.81% of JavaScript online submissions for Climbing Stairs.

也可以直接用公式：

$$F_n = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1})$$

var climbStairs = function(n) {
  const constant = 1 / Math.sqrt(5);
  const equ =
    Math.pow((1 + Math.sqrt(5)) / 2, n + 1) -
    Math.pow((1 - Math.sqrt(5)) / 2, n + 1);
  return constant * equ;
};

理论上似乎可以，但js的计算不怎么给力。

image-20190716161152668

参考这个库，对小数点进行处理

var climbStairs = function(n) {
  const constant = 1 / Math.sqrt(5);
  const equ =
    Math.pow((1 + Math.sqrt(5)) / 2, n + 1) -
    Math.pow((1 - Math.sqrt(5)) / 2, n + 1);
  const result = constant * equ;
  return parseFloat(result.toPrecision(12));   // 处理一下最后的结果
};

Runtime: 40 ms, faster than 99.74% of JavaScript online submissions for Climbing Stairs.

Memory Usage: 33.8 MB, less than 71.16% of JavaScript online submissions for Climbing Stairs.

Binets 方法

这个感觉很牛逼，用矩阵的乘法来解题。。