前言

本文正在参与掘金团队号上线活动，点击查看大厂春招职位。

题目

假设你正在爬楼梯。需要 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从1-6为例子来画一个表格。

n=1

n=2

总的方案：1 + 1 = 2

n=3

总的方案： C33 + C21 = 1 + 2 = 3

n=4

总的方案： C44+C31+C22 = 1 + 3 + 1 = 5

n=5

总的方案： C55 + C41 + C32 = 1 + 4 + 3 = 8

n=6

总的方案：C66 + C51 + C42 + C33 = 1 + 5 + 6 + 1 = 13

所以从上面的总结你看出什么了么？本来准备用排列组合方式，结果一看这不就是斐波那契数列么？

然后我就唰唰地按照这个思路写了以下代码，心里美滋滋：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let res;

    if (n===1) return 1;
    if (n===2) return 2;

    res = climbStairs(n-1) + climbStairs(n-2);

    return res;
};
复制代码

不幸的是，竟然超时了！可能是调用太多递归的原因！
然后我就网上开始各种搜索，找到了相关的解题思路，也就是动态规划的思想！

可以参考此文章。

我稍微提一下这个动态规划的思想，其实它是为了节省时间、空间复杂度做的优化，把上一次拿到的计算结果存起来，这样就不用下次再次计算，然后顺着往前推，走到第n阶，第n阶的走法，一定是n-1阶的走法加上n-2的走法。下面我们再来看看代码上它是如何去动态规划往前推的。

AC代码

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1 || n === 2) return n;

    let a = 1;
    let b = 2;
    let temp = 0;

    for(let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }

    return temp;
};
复制代码

总结

这是一道一看以为是数学题的算法题，结果真的是大意了，大意了，明眼人一看就知道是递归思想，谁能料到竟然会超时，涉及到了动态规划的思想，以前确实从未接触过这个思想，今天真是学到了。