本题来自LeetCode70. 爬楼梯，难度简单，属于一道动态规划的入门题，题目描述如下：
假设你正在爬楼梯。需要 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 阶
我们简单分析题目，然后解决此题。
贰 ❀ 斐波那契数列与动态规划
其实在JS 从斐波那契数列浅谈递归一文中，我就曾谈到过爬楼梯的问题，那时候18年，我还是个连算法是啥都不知道的小菜鸡...而这篇文章也记录了当时我对于爬楼梯的问题的思考，通过推导也简单介绍了斐波那契数列，以及如何利用递归解决此问题。但比较遗憾的是，当时的递归做法过于暴力，用于此题的答案会直接爆栈。所以这里我们尝试用动态规划的思路解决它。
对于动态规划，我们总是尝试将大问题拆分成小问题，站在小问题的角度推导动态转移公式，从而达到解决全局问题的目的，在上面的文章中其实也详细介绍了公式推导的过程（图文并茂！！），有兴趣可以看看，这里我们简单推导下这个过程：
因为题目说了爬楼梯一次只能走一格，或者两格，于是有了如下过程：
- 当只有一阶楼梯，只有1种方式。
- 当有两阶楼梯，我们可以1 1的爬，也可以直接2跨两阶，因此是2种方式。
- 三阶楼梯，我们可以1 1 1，1 2，或者2 1，因3种方式。
- 四阶楼梯，我们可以1 1 1 1，1 2 1，2 1 1，1 1 2，2 2，因此是5种。
如果你继续往下推导，会发现从三阶开始，这一阶爬楼梯的方式等于前两阶方式的和，因此我们得出公式，当然，我们得从第三阶开始才能满足。：
dp[i] = dp[i-1] + dp[i-2]
那么如何利用此公式解决这个问题呢？我们设想一想，假设有个数组，依次保存了每阶楼梯的爬法，那么如果要知道第 i 阶的有多少种方法，我们只要知道 [i-1]与[i-2]的方法的和即可，反过来说，我们知道了[i]的次数，那么它也能为后续的楼梯次数计算提供帮助。
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
// 特化处理，少于2直接返回
if (n <= 2) {
return n;
};
// 为了方便理解，我们i对应的就是第i阶的爬法，所以数组储存肯定是从1开始有效，因此得多简历一个，0位是废弃位。
let dp = new Array(n + 1);
//这两个是已知的，为后续计算服务
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
};
return f[n];
};
上述代码应该是很直观的动态规划，i从3开始是因为第三阶开始才满足上述推导公式。而dp[1]与dp[2]的初始化，单纯是为了后续计算铺路，那么一道简单的爬楼梯就说到这里了。
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
