爬楼梯题目来源：https://leetcode-cn.com/problems/climbing-stairs题目假设你正在爬楼梯。需要走n步才能到达建筑物的顶部。您一次可以爬1或2个台阶。您可以通过多少种不同的方式到达建筑物的顶部？注：给定的n为正整数。示例1：输入：2输出：2解释：有两种方法可以到达建筑物的顶部。1.Step1+Step12.Step2示例2：输入：3输出：3解释：有三种方法可以爬到建筑物的顶部。1.1storder+1storder+1storder2.1storder+2ndorder3.2ndorder+1storder动态规划解题思路其实这道题可以分解成多个子问题，最优解构造自子问题的最优解；例如爬第i阶梯，有两种选择：爬到第(i-1)步，再爬第1步到达第i阶；爬到(i-2)步，然后爬2步到达i-step；情况，可以得到爬到第i层，即方法数到(i-1)和(i-2)的总和；用公式表示：dp[i]=dp[i-1]+dp[i-2]。代码实现类Solution:defclimbStairs(self,n:int)->int:'''计算爬楼梯的方式数args:n:表示楼梯的步数returns:返回爬n步的方式数ofstairs'''#如果步数n小于2，直接返回nifn<=2:returnn#将问题分解为多个子问题#爬第i步楼梯可以分解为攀爬方法之和(i-1)和(i-2)#定义链表索引为步数，当n为0时，这里直接赋None#只给索引为1的两个元素赋值and2dp=[None,1,2]foriinrange(3,n+1):dp.append(dp[i-1]+dp[i-2])returndp[n]达到效果斐波那契数解题思路根据上述动态规划公式，dp[i]=dp[i-1]+dp[i-2]可以看出dp[i]是第i个斐波那契数；于是可以得到公式Fib[i]=Fib[i-1]+Fib[i-2];现在的问题是求第n个第一项为1，第二项为2的斐波那契数，且Fib[1]=1，Fib[2]=2。代码实现类Solution:defclimbStairs(self,n:int)->int:'''计算爬楼梯的方式数args:n:表示楼梯的步数returns:返回爬n步的方式数ofstairs'''#如果步数n小于2，直接返回nifn<=2:returnn#将问题分解为多个子问题#爬第i步楼梯可以分解为爬(i-1)和(i-2)的方法之和#即求第n个第一项为1，第二项为2的斐波那契数a,b=1,2for_inrange(3,n+1):a,b=b,b+areturnb实现效果以上是本文的主要内容题外话：越是恐慌，谣言就越多。目前尽量不出门，照顾好自己，就是对社会最大的贡献。欢迎关注微信公众号《书所集录》
