时间戳

首页 > 解决方案 > 为什么我在 LeetCode 上的解决方案不起作用（递归、python）？

python - 为什么我在 LeetCode 上的解决方案不起作用（递归、python）？

问题描述

class Solution:

    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            return self.climbStairs(n - 1) + self.climbStairs(n - 2)

然而，我的解决方案不适用于 Leetcode。你知道这是为什么吗？太感谢了！

我正在尝试解决斐波那契数列

标签： pythonrecursion

解决方案

你选择了一个糟糕的算法。并不是它是递归的，只是非常低效。这是一种更有效的递归方法：

def climbStairs(self, n, res=1, nxt=1):
    if n == 0:
        return res
    return self.climbStairs(n - 1, nxt, res + nxt)

这比您的代码运行得快得多，并且在堆栈溢出之前可以走得更高。但它最终会发生堆栈溢出。我们可能会更好地添加记忆，但最终，一个简单的迭代解决方案会更容易：

def climbStairs(self, n):  # doesn't use 'self', could be class method
    if 0 <= n <= 1:
        return 1

    a = b = 1

    for _ in range(n - 1):
        a, b = b, a + b

    return b

推荐阅读