标题二：
思路
本题咱们假如没有接触过的话，会感觉比较难，多举几个例子，就能够发现其规则。
爬到第一层楼梯有一种办法，爬到二层楼梯有两种办法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状况能够由第二层楼梯 和 到第一层楼梯状况推导出来，那么就能够想到动态规划了。
咱们来剖析一下，动规五部曲：
界说一个一维数组来记录不同楼层的状况
- 确定dp数组以及下标的意义
dp[i]： 爬到第i层楼梯，有dp[i]种办法
- 确定递推公式
假如能够推出dp[i]呢？
从dp[i]的界说能够看出，dp[i] 能够有两个方向推出来。
首先是dp[i – 1]，上i-1层楼梯，有dp[i – 1]种办法，那么再一步跳一个台阶不便是dp[i]了么。
还有便是dp[i – 2]，上i-2层楼梯，有dp[i – 2]种办法，那么再一步跳两个台阶不便是dp[i]了么。
那么dp[i]便是 dp[i – 1]与dp[i – 2]之和！
所以dp[i] = dp[i – 1] + dp[i – 2] 。
在推导dp[i]的时分，一定要时刻想着dp[i]的界说，否则简单跑偏。
这体现出确定dp数组以及下标的意义的重要性！
- dp数组怎么初始化
在回忆一下dp[i]的界说：爬到第i层楼梯，有dp[i]中办法。
那么i为0，dp[i]应该是多少呢，这个能够有许多解说，但都基本是直接奔着答案去解说的。
例如强行安慰自己爬到第0层，也有一种办法，什么都不做也便是一种办法即：dp[0] = 1，相当于直接站在楼顶。
但总有点勉强的成分。
那还这么了解呢：我就以为跑到第0层，办法便是0啊，一步只能走一个台阶或许两个台阶，可是楼层是0，直接站楼顶上了，便是不用办法，dp[0]就应该是0.
其实这么争辩下去没有意义，大部分解说说dp[0]应该为1的理由其实是由于dp[0]=1的话在递推的过程中i从2开端遍历本题就能过，然后就往结果上靠去解说dp[0] = 1。
从dp数组界说的角度上来说，dp[0] = 0 也能说得通。
需求留意的是：标题中说了n是一个正整数，标题根本就没说n有为0的状况。
所以本题其实就不应该评论dp[0]的初始化！
我相信dp[1] = 1，dp[2] = 2，这个初始化咱们应该都没有争议的。
所以我的原则是：不考虑dp[0]假如初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开端递推，这样才契合dp[i]的界说。
- 确定遍历次序
从递推公式dp[i] = dp[i – 1] + dp[i – 2];中能够看出，遍历次序一定是早年向后遍历的
- 举例推导dp数组
举例当n为5的时分，dp table（dp数组）应该是这样的
假如代码出问题了，就把dp table 打印出来，看看究竟是不是和自己推导的一样。
此刻咱们应该发现了，这不便是斐波那契数列么！
仅有的区别是，没有评论dp[0]应该是什么，由于dp[0]在本题没有意义！
以上五部剖析完之后，JS代码如下：
var climbStairs = function(n) {
// dp[i] 为第 i 阶楼梯有多少种办法爬到楼顶
// dp[i] = dp[i - 1] + dp[i - 2]
let dp = [1, 2]
for (let i = 2; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n - 1]
};
当然依然也能够，优化一下空间复杂度，代码如下：
var climbStairs = function(n) {
if (n === 1) return 1
let dp = [0, 1, 2]
for (let i = 3; i <= n; i++) {
let sum = dp[1] + dp[2]
dp[1] = dp[2]
dp[2] = sum
}
return dp[2]
};
- 时刻复杂度：O(n)O(n)
- 空间复杂度：O(1)O(1)
后面将解说的许多动规的标题其实都是当前状况依靠前两个，或许前三个状况，都能够做空间上的优化，但我个人以为面试中能写出版别一就够了哈，清晰明晰，假如面试官要求进一步优化空间的话，咱们再去优化。
由于版别一才干体现出动规的思想精髓，递推的状况改变。
拓宽
这道标题还能够持续深化，便是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种办法爬到n阶楼顶。
这又有难度了，这其实是一个完全背包问题，但力扣上没有这种标题，所以后续我在解说背包问题的时分，今日这道题还会拿从背包问题的角度上来再讲一遍。
这里我先给出我的实现代码：
var climbStairs(int n) {
let dp = new Array(n + 1).fill(0)
dp[0] = 1
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) { // 把m换成2，就能够AC爬楼梯这道题
if (i - j >= 0) dp[i] += dp[i - j]
}
}
return dp[n]
}
代码中m表明最多能够爬m个台阶。
以上代码不能运行哈，我首要是为了体现只要把m换成2，粘曩昔，就能够AC爬楼梯这道题，不信你就粘一下试试，哈哈。
此刻我就发现一个绝佳的大厂面试题，第一道题便是单纯的爬楼梯，然后看提名人的代码实现，假如把dp[0]的界说成1了，就能够发难了，为什么dp[0]一定要初始化为1，此刻可能提名人就要强行给dp[0]应该是1找各种理由。那这便是一个考察点了，对dp[i]的界说了解的不深化。
然后能够持续发难，假如一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种办法爬到n阶楼顶。这道标题leetcode上并没有原题，绝对是考察提名人算法才干的绝佳好题。
这一连套问下来，提名人算法才干怎么，面试官心里就有数了。
其实大厂面试最喜欢问题的便是这种简单题，然后慢慢改变，在小细节上考察提名人。
#总结
这道标题和动态规划：斐波那契数(opens new window)标题基本是一样的，可是会发现本题比较动态规划：斐波那契数(opens new window)难多了，为什么呢？
关键是动态规划：斐波那契数(opens new window)标题描述就已经把动规五部曲里的递归公式和怎么初始化都给出来了，剩余几部曲也自可是然的推出来了。
而本题，就需求逐一剖析了，咱们现在应该开始感触出关于动态规划，你该了解这些！(opens new window)里给出的动规五部曲了。
简单题是用来把握办法论的，例如昨天斐波那契的标题够简单了吧，但昨天和今日能够运用一套办法剖析出来的，这便是办法论！
所以不要轻视简单题，那种凭感觉就刷曩昔了，其实和没把握区别不大，只有把握办法论并说清一二三，才干举一反三，举一反三哈！
就酱，循序渐进学算法，认准「代码随想录」！
