python - 优于 LeetCode 的 'climbing stairs' pr*blem 的深度优先搜索解决方案

Question

我在 LeetCode 上做题，Climbing Stairs ，内容如下:

我想出了以下基于深度优先搜索的解决方案:

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        stack = [Node()]
        ways = 0
        while stack:
            node = stack.pop()
            if node.reached_top(n):
                ways += 1
            stack.extend(node.get_neighbors(n))
        return ways


class Node(tuple):
    def get_neighbors(self, n):
        return [Node(list(self) + [steps]) for steps in (1, 2) if sum(self) + steps <= n]

    def reached_top(self, n):
        return sum(self) == n

例如，Solution().climbStairs(2) == 2 和 Solution().climbStairs(3) == 3 根据需要。问题是这个解决方案超过了 35 输入的时间限制:

深度优先搜索似乎是解决这个问题的一种相当有效的算法，但显然，事实并非如此；关于如何改进我的解决方案的任何想法？

Answer 1

最简单的方法是根据 solution(n) = solution(n-1) + solution(n-2) 这一事实来计算每个答案。从 solution(1) = 1 和 solution(2) = 2 开始，您可以轻松计算出 solution(3)， solution(4) 等。根据需要计算该数组。

这段代码会足够快。

实现后谷歌的方向是“动态规划”和“斐波那契数列”。在这两者中，动态规划是更重要的学习内容。