LeeCode 的 Python 实现 70: 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

爬楼梯问题的实质就是 斐波那契数列
f(n) = f(n-1) + f(n-2)

递归实现

最先想到的就是简单粗暴的递归方式实现.

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if(n == 1 or n == 0):
            return 1
        else:
            # 假如不是以类的形式, 直接 return 函数() 不需要加 self.
            return self.climbStairs(n-1) + self.climbStairs(n-2)

显然这种方式是无法通过 LeeCode 测试的, 绝对超时. 就算不超时换个大一点的数也会栈溢出.

关于 Python 的尾递归方式实现可以参考廖雪峰老师的文章 - 递归函数

非递归实现

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if(n == 1 or n == 0):
            return 1
        
        temp = [1, 1]
        result = 0
        
        while(n > 1):
            result = temp[-1] + temp[-2]
            temp[-1] = temp[-2]
            temp[-2] = result
            n = n - 1
        
        return result