比 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) 等。根据需要计算该数组。

这段代码会足够快。

实施后Google的方向是"dynamic programming"和"Fibonacci sequence"。两者之中，动态规划是更重要的学习内容。

Answer 2

在上面的解决方案中，您通过生成它们来计算每一种可能性。如果你计算 climbStairs(35) 那么它应该等于 14930352。所以这里让我们假设您的函数是 f(n)，它计算爬升到 stair-N 的可能方式。说明：您的解决方案中发生了什么：

// assuming f(x) = 0 where x <= 0 
// and f(1) = 1 && f(2) = 2;
f(n) = f(n-1) + f(n-2); 
f(n-1) = f(n-2) + f(n-3);
f(n-2) = f(n-3) + f(n-4);
.
.
.
f(2) = 2;
f(1) = 1;

所以在这里你可以看到你在一次又一次地计算相同的部分，比如 f(n-1) 和 f(n-2)。

您可以通过保存达到特定 stair-X 的可能组合来避免那些 re-calculations。这是我在 Java 中的解决方案。使用 "dynamic-programming" 方法。要计算 climbStairs(35)，它总共需要 35 个步骤（而不是 8 位的大数字）。

public int climbStairs(int n) {
    int dp[] = new int[n+1];
    if(n==1) {
        return 1;
    } else if(n==2){
        return 2;            
    } else {
        dp[1] = 1;
        dp[2] = 2;

        for(int i =3; i<=n;i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

Answer 3

为了扩展 btilly 的答案，假设达到 n 步的方法数是 solution(n)。在第一步中，您可以迈出长度 1 的步长并剩余 solution(n-1) 路，或者迈出长度 2 的步长并剩余 solution(n-2) 路。由于两者是互斥的，所以剩下的方式总数是solution(n-1) + solution(n-2)。

我决定使用简单的递归函数，而不是他描述的 'bottom-up' 动态规划方法，并使用来自 https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize 的 memoize class 进行记忆。这是我的解决方案：

import collections
import functools


class memoized(object):
    '''Decorator. Caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned
    (not reevaluated).
    '''
    def __init__(self, func):
       self.func = func
       self.cache = {}
    def __call__(self, *args):
       if not isinstance(args, collections.Hashable):
          # uncacheable. a list, for instance.
          # better to not cache than blow up.
          return self.func(*args)
       if args in self.cache:
          return self.cache[args]
       else:
          value = self.func(*args)
          self.cache[args] = value
          return value
    def __repr__(self):
       '''Return the function's docstring.'''
       return self.func.__doc__
    def __get__(self, obj, objtype):
       '''Support instance methods.'''
       return functools.partial(self.__call__, obj)


class Solution(object):
    @memoized
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

这个方案被LeetCode接受：

比 LeetCode 的 'climbing stairs' pr*blem 的深度优先搜索解决方案更好

Better than depth-first search solution to LeetCode's 'climbing stairs' pr*blem

python

algorithm

depth-first-search

asymptotic-complexity