美文网首页
70. 爬楼梯(easy)

70. 爬楼梯(easy)

作者: genggejianyi | 来源:发表于2019-06-02 22:50 被阅读0次

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
    注意:给定 n 是一个正整数。
    示例 1:
    输入: 2
    输出: 2
    解释: 有两种方法可以爬到楼顶。

    1. 1 阶 + 1 阶
    2. 2 阶
      示例 2:
      输入: 3
      输出: 3
      解释: 有三种方法可以爬到楼顶。
    3. 1 阶 + 1 阶 + 1 阶
    4. 1 阶 + 2 阶
    5. 2 阶 + 1 阶
    • show the code:
    ### code1
    class Solution:
        def climbStairs(self,n):
            if n == 1:
                return 1
            if n == 2:
                return 2
            return self.climbStairs(n-1)+self.climbStairs(n-2)
    
    ### code2
    class Solution:
        def climbStairs(self, n: int) -> int:
            a,b = 1,2
            if n == 1:
                return a
            if n == 2:
                return b
            for i in range(n-2):
                a,b = b,a+b
            return b
    
    • 此题是经典题,一看到题就应该联想到斐波拉契数列。代码一是最直接的解法,但是会重复地求很多次中间值,所以时间复杂度在2^n指数级别,所以肯定是不理想的,甚至都不能AC。
    • 代码二则省去了计算重复值,而且不用储存中间值,只需要储存前两个值即可,因此在时间和空间上都有较大提升。
    • 有关此类题目的解法在力扣官方题解上有很多方法,其中像矩阵法和公式法都只需要logn的复杂度。链接如下:爬楼梯方法

    相关文章

      网友评论

          本文标题:70. 爬楼梯(easy)

          本文链接:https://www.haomeiwen.com/subject/gbbfxctx.html