关于前端:有趣的算法『爬楼梯』

5次阅读

共计 1731 个字符，预计需要花费 5 分钟才能阅读完成。

这道题最后是在一个孙红雷演的电影《少年班》外面看到的，过后没搞懂怎么解决，但有了一个印象，起初再遇到的时候就感觉很乏味，值得钻研一下。

假如你正在爬楼梯。须要 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

这道题的难度是 Easy，然而我第一次见到的时候并没有想到方法，起初看到他人的解法才感到豁然开朗，咱们一步步来。

说下这道题的思路：上第 N 阶台阶的话，最初一步只能是迈 1 阶或者 2 阶这两种状况，所以到 N 阶台阶的所有办法等于到 N-1 阶和到 N-2 阶的所有办法的和。

转化成公式就是：f(N)=f(N-1)+f(N-2)，f(N)的意思是到 N 阶台阶的所有办法数

已知：f(1)=1和f(2)=2，上代码

var climbStairs = function (n) {if (n === 1) {return 1;}
  if (n === 2) {return 2;}
  return climbStairs(n - 1) + climbStairs(n - 2);
};

测试下，后果在算 45 阶的时候超时了，下一步须要思考怎么优化

咱们能够看到，依照下面的思路是没有问题的，只是运算超时了，那么就须要思考下怎么放慢运算，咱们能够尝试画出求解的整个过程，来寻找优化的思路。

通过上图咱们能够看到，f(45) = f(43)+f(44) , 而后能够持续合成：

f(45) = f(43) + f(44);
f(45) = f(41) + f(42) + f(42) + f(43);
// .....
// .....
// .....
// 最初合成到了已知值，即：f(1) = 1;
f(2) = 2;

在整个合成的过程中，咱们会发现其实有一些反复的值，比方下面的 f(42) 求解了两次，而且 f(42) 和f(43)会持续合成出反复的值。

那么咱们能够想方法不去求解反复的值，利用曾经求解结束的值做一个备份，发现曾经求解的间接拿来用，上代码。

let dp = new Map();
dp.set(1, 1).set(2, 2);

var climbStairs = function (n) {if (dp.has(n)) {return dp.get(n);
  }
  let result = climbStairs(n - 1) + climbStairs(n - 2);
  dp.set(n, result);
  return result;
};

提交后的后果：

45/45 cases passed (92 ms)
Your runtime beats 9.54 % of javascript submissions
Your memory usage beats 42.58 % of javascript submissions (37.5 MB)

还能够，终于不是超时了，然而后果来看，咱们的排名并不靠前，那么还有持续优化的空间了吗？

咱们发现，求解结束一个 f(45) 之后，dp 外面记录了从 f(1)到 f(45)的所有的值，实际上咱们只想要 f(45) 的值。

咱们换个思路，求 f(45) 的过程，合成为先求f(3)，而后再求f(4)…… 始终到f(45)，上代码：

var climbStairs = function (n) {if (n === 1 || n === 2) {return n;}
  // 前一个值
  let pre = 2;
  // 前一个的前一个的值
  let beforePre = 1;
  // 两头变量
  let temp = null;
  for (let index = 3; index <= n; index++) {
    temp = pre;
    pre = pre + beforePre;
    beforePre = temp;
  }
  return pre;
};

提交下看看后果：