# 70. 爬楼梯 (opens new window)
# 题目描述
假设你正在爬楼梯。需要 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 阶
相关信息：
- 难度：简单
- 标签：动态规划
# 题解
这是一道最经典最入门的动态规划题目，值得好好研究。首先我们来分析一下前几阶的盘楼梯方法：
记台阶数为 n，方法数为 f(n)，则：
当 n = 1 时，爬上第 1 阶的方法当然只有一种，故 f(1)=1;
当 n = 2 时，爬上第 2 阶的方法有两种：分别时一阶一阶地爬上第 2 阶和跨两阶直接上第 2 阶；故 f(2)=2；
当 n = 3 时，爬上第 3 阶的方法也有两种，分别是从第 1 阶直接跨两阶上第 3 阶和从第 2 阶跨一阶上第 3 阶；故 f(3)=f(2)+f(1)=3；
后面所有阶和第 3 阶几乎一致。
从上面的分析可知：f(n)=f(n-1)+f(n-2)。
# 方法一：递归
把方法数 f(n) 看作我们的执行函数，我们可以很轻易想到使用递归的方法可以实现，下面使用最基本的递归实现：
var climbStairs = function (n) {
//递归：超时
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
};
很不幸，它超时了。当我们分析它的执行过程时，你就会发现它超时的原因，比如 n=5 时，它会去计算 n=3 和 n=4 的结果；而当它计算 n=4 时，它又会去计算 n=3 和 n=2 的结果。不知道你有没有发现问题所在，n=3 的情况在所有大于它的情况中都会重复计算一次，这就拖累了程序执行速度。
所以我们可以想办法将前面已经计算过的一些结果保留下来，避免重复计算，这里我们使用了一个数组来记忆这些结果：
var climbStairs = function (n) {
//记忆化递归
let memo = [0, 1, 2]; //记忆数组
function climbStairsWithMemo(n, memo) {
if (memo[n]) {
return memo[n];
}
memo[n] =
climbStairsWithMemo(n - 1, memo) + climbStairsWithMemo(n - 2, memo);
return memo[n];
}
return climbStairsWithMemo(n, memo);
};
上述代码中的记忆数组的下标和 n 是对应的，所以 memo[1] 代表 n=1 时的方法数。其实不存在 n=0 的情况，但是这里设置 memo[0]=0 只是为了占位，没有特殊含义。
# 方法二：动态规划
如果我们将 f(n) 视作一个状态，那么由前文分析出来的 f(n)=f(n-1)+f(n-2) 可知，f(n)这个状态是由 f(n-1) 和 f(n-1) 两个状态转变而来的。所以动态规划本质是状态的改变，关键是找到状态改变的方程。
var climbStairs = function (n) {
//动态规划
let dp = [0, 1, 2]; //dp数组
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
在上述代码中，我们同样使用了一个数组来记录动态规划过程中各个状态的值，用于计算后面的状态值。然后使用一个 for 循环去迭代这个 dp 数组，直到计算出我们想要的 dp[n] 的值。看到这，不知道有没有感觉这段代码的逻辑和上边那段带代码逻辑是完全一致的，只是使用了两种完全不同的实现方式，一种是迭代，一种是递归。其中递归是从 n 开始建立递归调用栈，一层层计算至 n=1，然后将每一层的结果返回至上一层，直至返回到 n 阶得出结果，所以这个过程是有一来一回两部分哒。而迭代是直接从 n=1 的状态，一层层迭代至 n。故它的过程是一个单向过程。所以理论上来说，动态规划执行速度应该是强于递归哒。
那么上方代码是否就是完美无缺的呢？是否还有可优化的空间呢？当然，通过前面的分析，我们知道，f(n) 这个状态只与 f(n-1) 和 f(n-2) 两个状态有关，与其他保存的状态无关，而最终的返回值要求返回的是最终的状态值，而非整个过程的全部状态值。故其实我们不必保存整个状态，只需要保存与当前状态相关的前两个状态就好啦。这样就可以极大地优化空间复杂度。
var climbStairs = function (n) {
if (n === 1) return 1;
let first = 1; //保存的第一个状态
let second = 2; //保存的第二个状态
let third; //当前状态
for (let i = 3; i <= n; i++) {
third = first + second;
first = second;
second = third;
}
return second;
};
而这便是动态规划中常见的优化方式——状态压缩。上面代码中我们还是保留了三个状态，主要是为了方便交换前两个状态，如果你想做得更极客一点儿，甚至可以压缩到只保留两个状态。
var climbStairs = function (n) {
if (n === 1) return 1;
let first = 1; //保存的第一个状态
let second = 2; //保存的第二个状态
for (let i = 3; i <= n; i++) {
second += first;
first = second - first;
// 等价于 [first, second] = [second, first + second]
}
return second;
};
# 方法三：斐波拉契数列
如前文所言，当我们只保存前两个状态时，我们先写将上文中的 dp 数组前几轮状态写出来看看：
dp=[0,1,2,3,5,8]
是否有觉得眼熟呢？没有吗？那如果把第一个元素改为 1 呢？
dp=[1,1,2,3,5,8]
这下很眼熟了吧？没错就是中学时数学推断题目中最经典的斐波拉契数列呀！在前面的分析我们也说了，在本题中 dp[0] = 0 是没有特殊意义的，只一个占位符而已，那么我们将这个占位符改为 1 也是没有关系的。而一旦改为 1，你就会发现，它是完全满足斐波拉契数列规律的。
var climbStairs = function (n) {
//斐波拉契数列
let first = 1; //以1占位，便能满足斐波拉契数列
let second = 1;
for (let i = 2; i <= n; i++) {
second += first;
first = second - first;
}
return second;
};
以上的方法和思路都是比较正常的编程思路，而下面的方法就更加数学化了，需要极其深厚的数学理论知识，看不懂的同学了解一二即。因为我也看不懂，哈哈哈，数学菜鸡在线哭泣！不过，将问题和数学理解结合，使用理论推导出简洁的公式，进而优化编码，我认为这是一个很好的尝试方向，也许不止这一道题目可以与数学理论结合。如果有兴趣的同学，可探索一二，验证我的想法是否正确。至于我嘛，就接着啃我的《高数》《线性代数》的教材吧！哈哈哈。
# 方法四：矩阵快速幂
这一块儿内容，我并没有完全消化，便不再班门弄斧了，想详细了解的同学直接查看官方题解吧
//来自官方体题解：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
var climbStairs = function (n) {
const q = [
[1, 1],
[1, 0],
];
const res = pow(q, n);
return res[0][0];
};
const pow = (a, n) => {
let ret = [
[1, 0],
[0, 1],
];
while (n > 0) {
if ((n & 1) === 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
};
const multiply = (a, b) => {
const c = new Array(2).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
};
# 方法五：通项公式
如方法四一样，直接查看官方题解吧。
//来自：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
var climbStairs = function (n) {
const sqrt5 = Math.sqrt(5);
const fibn =
Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
return Math.round(fibn / sqrt5);
};
以上就是本题的所有题解啦，感谢你能看到这里，如果本文对你有所帮助的话，别忘了给一个 Star 嗷～ 如果你对题解中的代码有不一样的优化意见，也欢迎你在 issue 中指出～ 最重要的是不要忘了点点关注嗷（Github (opens new window)、力扣 (opens new window)），以便获取我最新的题解以及文章通知。
# 参考：
# 全部代码
/*
* @lc app=leetcode.cn id=70 lang=javascript
*
* [70] 爬楼梯
*
* https://leetcode-cn.com/problems/climbing-stairs/description/
*
* algorithms
* Easy (51.82%)
* Likes: 1623
* Dislikes: 0
* Total Accepted: 427.1K
* Total Submissions: 823.9K
* Testcase Example: '2'
*
* 假设你正在爬楼梯。需要 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 阶
*
*
*/
// @lc code=start
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
//斐波拉契数列
let first = 1;//以1占位，便能满足斐波拉契数列
let second = 1;
for (let i = 2; i <= n; i++) {
second += first;
first = second - first;
}
return second;
};
// @lc code=end
var climbStairs = function (n) {
//递归：超时
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
};
var climbStairs = function (n) {
//记忆化递归
let memo = [0, 1, 2];
function climbStairsWithMemo(n, memo) {
if (memo[n]) {
return memo[n]
}
memo[n] = climbStairsWithMemo(n - 1, memo) + climbStairsWithMemo(n - 2, memo);
return memo[n]
}
return climbStairsWithMemo(n, memo);
};
var climbStairs = function (n) {
//动态规划
let dp = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
var climbStairs = function (n) {
//dp状态压缩
if (n === 1) return 1;
let first = 1;
let second = 2;
let third
for (let i = 3; i <= n; i++) {
third = first + second;
first = second;
second = third;
}
return second;
};
var climbStairs = function (n) {
//斐波拉契数列
let first = 1;//以1占位，便能满足斐波拉契数列
let second = 1;
let third
for (let i = 2; i <= n; i++) {
third = first + second;
first = second;
second = third;
}
return second;
};
var climbStairs = function (n) {
if (n === 1) return 1;
let first = 1;//保存的第一个状态
let second = 2;//保存的第二个状态
for (let i = 3; i <= n; i++) {
second += first;
first = second - first;
//[first, second] = [second, first + second]
}
return second;
};