假设你正在爬楼梯。需要走n步才能到达建筑物的顶部。您一次可以爬1或2个台阶。你有多少种不同的方式可以爬到建筑物的顶部？注：给定n为正整数。示例1：输入：2输出：2解释：有两种方法可以到达建筑物的顶部。1.1storder+1storder2.2ndorder示例2：输入：3输出：3解释：有三种方式可以爬到楼顶。1.1st+1storder+1storder2.1storder+2ndorder3.2ndorder+1storder解法：动态规划动态规划（DynamicProgramming，DP）是一种将复杂问题分解为小问题的策略，但它不同于分治算法有趣的是，分治算法要求各个子问题相互独立，而动态规划的各个子问题是相互关联的。divideandconquer，顾名思义，就是分而治之，把一个复杂的问题分成两个或多个相似的子问题，再把子问题分成更小的子问题，直到更小的子问题可以简单解决为止，并求解子问题，那么原问题的解就是子问题解的组合。当我们使用动态规划求解问题时，需要遵循以下重要步骤：由题可知：最后一步可能需要2步或1步，即第n步的计划数等于第n-1步的计划数加上第n步的计划数第二步：实现需要反复求解的子子问题dp[n]=dp[n?1]+dp[n?2]第三步：识别并求解边界条件//Level0and1solutiondp[0]=1//Level1也是1solutiondp[1]=1最后一步：将尾部代码翻译成代码并处理一些边界条件letclimbStairs=function(n){letdp=[1,1]for(leti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]}returndp[n]}复杂度分析：时间复杂度：O(n)空间复杂度：O(n)优化空间复杂度：letclimbStairs=function(n){letres=1,n1=1,n2=1for(leti=2;i<=n;i++){res=n1+n2n1=n2n2=res}returnres}空间复杂度：O(1)leetcode：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-wen-ti-by-user7746o/
