来自力扣官网：
https://leetcode-cn.com/problems/climbing-stairs/
1
问题描述
假设你正在爬楼梯。需要
n
阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：
给定
n
是一个正整数。
2
解决方法
（1）动态规划
这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，使用
动态规划
来解决这一问题。
第 i阶可以由以下两种方法得到：
在第 (i−1) 阶后向上爬1阶。
在第 (i−2) 阶后向上爬2阶。
所以到达第i 阶的方法总数就是到第 (i−1) 阶和第 (i−2) 阶的方法数之和。
令dp[i]表示能到达第i 阶的方法总数：
dp[i]=dp[i-1]+dp[i-2]
其中时间和空间复杂度都是o（n）
（2）裴波那契数法
分析问题和上面一样。可以很容易通过分析得出dp[i] 其实就是第i个斐波那契数。
Fib(n)=Fib(n-1)+Fib(n-2)
现在我们必须找出以1和2作为第一项和第二项的斐波那契数列中的第 n 个数，也就是说 Fib(1)=1且Fib(2)=2。
时间和空间复杂度分别是o（n）、o（1）
3代码（三种方法）
/**
问题描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
实例：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
https://leetcode-cn.com/problems/climbing-stairs/
*/
function calculateClimbStairs(n) {
//使用动态规划的方法；时间复杂度是o（n），空间也是o（n）
//n表示楼梯数
if(n === 1){
return 1;
}
let result = []; //用数组result保存1-n个楼梯时走路的种数
result[1] = 1; //为了方便，数组下标从1开始保存数值，第n个表示n步有几种走法
result[2] = 2;
for(let i = 3; i < n; i++){
result[i] = result[i - 1] + result[i - 2];
}
return result[n];
}
function climbStairs(n) {
//使用裴波那契法（可以使用递归，但是可能超时）
if(n === 1 || n === 2){
return n;
}
let result; //用来保存结果
let preTwo = 1; //需要记忆两个数
let preOne = 2;
for(let i = 3; i < n + 1; i++){
result = preOne + preTwo;
preTwo = preOne;
preOne = result;
}
return result;
}
function climbStairs_2(n) {
//递归算法（力扣里面超时啦）
if(n === 1 || n === 2){
return n;
}
return climbStairs_2(n - 1) + climbStairs_2(n - 2);
}
百里于2020年3月22日
参考：
力扣：
https://leetcode-cn.com/problems/climbing-stairs/
如果有错，请您指出！如有侵权，请联系我删除！