爬楼梯题目链接：https://leetcode-cn.com/problems/climbing-stairs假设你正在爬楼梯。需要走n步才能到达建筑物的顶部。您一次可以爬1或2个台阶。你有多少种不同的方式可以爬到建筑物的顶部？注：给定n为正整数。示例1：输入：2输出：2解释：有两种方法可以到达建筑物的顶部。Step1+Step1Step2示例2：输入：3输出：3解释：有三种方法可以到达建筑物的顶部。1storder+1storder+1storder1storder+2ndorder2ndorder+1storder如果你没有接触过这个问题，你会觉得很难。多举几个例子，找出其中的规律。有一种方法可以到达第一段楼梯，有两种方法可以到达第二段楼梯。然后在第一段楼梯上走两步到三楼，在第二段楼梯上再走一步到三楼。所以楼梯到三楼的状态可以从楼梯到二楼和楼梯到一楼的状态推导出来，那么可以想到动态规划。下面来分析一下动态规则的五个部分：定义一个一维数组记录不同楼层的状态确定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。在递归的过程中，我可以从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表（dp数组）应该是这样的。如果代码有问题，打印出dp表，看看是否和你推导的一样。这时候大家应该已经发现了，这就是斐波那契数列！唯一不同的是没有讨论dp[0]应该是什么，因为dp[0]在这道题中没有任何意义！以上五部分分析完后，C++的代码如下：//Version1classSolution{public:intclimbStairs(intn){if(n<=1)returnn;//因为下面直接对dp[2]进行操作，防止空指针vectordp(n+1);dp[1]=1;dp[2]=2;for(inti=3;i<=n;i++){//注意i开始来自3dp[i]=dp[i-1]+dp[i-2];}returndp[n];}};时间复杂度：空间复杂度：当然还是可以的，优化一下空间复杂度，代码如下：//version2classSolution{public:intclimbStairs(intn){if(n<=1)returnn;intdp[3];dp[1]=1;dp[2]=2;for(inti=3;i<=n;i++){intsum=dp[1]+dp[2];dp[1]=dp[2];dp[2]=sum;}returndp[2];}};时间复杂度：空间复杂度：后面要讲解的很多动态规则的题目，其实就是当前状态依赖于前两个或者前三个状态，可以做空间优化，但是个人觉得这样写就够了采访中的第一版。很清楚很清楚。如果面试官要求进一步空间优化，我们就去优化。只有版本1才能体现动态规则思想的本质，递归状态变化。要扩大这个题目，可以继续加深，也就是一步一步，两步，三步，直到有m步，有多少种方法可以爬到n步的顶端。这又难了。这其实就是一个完整的背包问题，但是里口上没有这个题目，所以后面讲解背包问题的时候，今天我就从背包问题的角度，再来说说这个问题。这里我先给出我的实现代码：classSolution{public:intclimbStairs(intn){vectordp(n+1,0);dp[0]=1;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){//把m改成2，就可以AC爬楼梯了if(i-j>=0)dp[i]+=dp[i-j];}}returndp[n];}};代码中的m表示最多可以爬m步。上面的代码运行不了，我主要是想说明只要把m换成2，贴上去，就可以AC爬楼梯了。不信你贴上试试看，哈哈。这时候，我发现了一道优秀的大厂面试题。第一道题就是简单的爬楼梯，然后看候选人的代码实现。如果dp[0]的定义是1，那就难了。为什么？dp[0]必须初始化为1，这时候考生可能会找各种理由强制dp[0]为1。那么这是一个调查点，dp[i]的定义不太好理解。然后可以继续挑战，如果一步是一步，两步，三步，直到m步，有多少种方法可以爬到n步的顶端。这道题leetcode上没有原题，绝对是考查考生算法能力的一道极佳题目。经过这一系列的问题，面试官就知道应聘者的算法能力了。其实大厂面试最喜欢的问题就是这样简单的问题，然后慢慢改成在小细节上考察候选人。总结一下这个题目和动态规划：斐波那契数列题目基本一样，但是你会发现这个题目比动态规划：斐波那契数列难多了，为什么？关键是动态规划：斐波那契数题目的描述已经给出了递归公式和如何初始化动态法则这五个部分，剩下的几部分自然展开。而这个问题需要一一分析。你现在应该对动态规划有了初步的感受。这些你要懂！中给出了动态规划的五个部分。使用简单的问题来掌握方法。比如昨天的斐波那契题，很简单，但是昨天和今天是可以用一套方法来分析的。这就是方法论！所以不要低估简单的问题。刷了之后，其实和没掌握没多大区别。只有掌握方法论，讲解一二三，才能举一反三，举一反三！就酱，一步步学算法，找《代码乱想》！其他语言版本JavaclassSolution{publicintclimbStairs(intn){//同斐波那契数列if(n<=2)returnn;inta=1,b=2,sum=0;for(inti=3;i<=n;i++){sum=a+b;a=b;b=sum;}returnb;}}//常规方式publicintclimbStairs(intn){int[]dp=newint[n+1];dp[0]=1;dp[1]=1;for(inti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}//替换数组withvariablerecordspublicintclimbStairs(intn){inta=0,b=1,c=0;//默认需要1次for(inti=1;i<=n;i++){c=a+b;//f(i-1)+f(n-2)a=b;//记录上一轮的值b=c;//后退1个数}returnc;}PythonclassSolution:defclimbStairs(self,n:int)->int:#dp[i]表示爬到第i层的楼梯种类数，(1,2)(2,1)是两种不同的种类dp=[0]*(n+1)dp[0]=1foriinrange(n+1):forjinrange(1,3):ifi>=j:dp[i]+=dp[i-j]returndp[-1]GofuncclimbStairs(nint)int{ifn==1{return1}dp:=make([]int,n+1)dp[1]=1dp[2]=2fori:=3;i<=n;i++{dp[i]=dp[i-1]+dp[i-2]}returndp[n]}JavascriptvarclimbStairs=function(n){//dp[i]是多少路s爬到第i个楼梯的顶端//dp[i]=dp[i-1]+dp[i-2]letdp=[1,2]for(leti=2;i
