爬楼梯
这道题最后是在一个孙红雷演的电影《少年班》外面看到的，过后没搞懂怎么解决，但有了一个印象，起初再遇到的时候就感觉很乏味，值得钻研一下。
假如你正在爬楼梯。须要 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;};提交下看看后果：
- 45/45 cases passed (76 ms)
- Your runtime beats 42.21 % of javascript submissions
- Your memory usage beats 79.72 % of javascript submissions (37.4 MB)
感觉还不错，下面的办法只用了 3 个变量，就从f(3)始终算到了 f(45)，工夫复杂度和空间复杂度都很低