1

问题是使用动态规划编写一个函数，用于爬升 N 步的方式数。鉴于一次只能爬 1 级或 2 级。

例如，如果 N=3，则函数应返回 [(1,1,1),(1,2),(2,1)]。我在 python 3 中编写了一个代码来计算。该代码运行良好，但与不使用动态编程的相同递归代码相比，当 N 达到 40 时，它需要相同的时间或 spyder(Anaconda) 应用程序崩溃。

它不应该比普通的更有效吗？

我在下面附上了 DP 代码

def stepsdyn(N,memo={}):
    """
    L1 is the list of all possibilities in the left side of the search tree,
    that is with 1 as the last element
    L2 is the list of all possibilities in the right side of the search tree
    memo stores the results of corresponding N
    returns memo[N]
    """
    L1=[]
    L2=[]
    if N==1:
        return [(1,)]
    elif N==0:
        return [()]
    else:
        try:
             return memo[N]
        except:
             for items in stepsdyn(N-1,memo):
                 items+=(1,)
                 L1.append(items)
             for items in stepsdyn(N-2,memo):
                 items+=(2,)
                 L2.append(items)
             memo[N]=L1+L2
             return memo[N]
4

2 回答 2

2

基本理念

在计算机编程中，最基本和最常见的权衡是时间效率和空间效率之间的权衡。记忆对时间有利，但对空间不利，这里就是这种情况。您的程序正在崩溃，因为该记忆字典包含大量数据。马上，您的重复关系意味着您永远不需要现场保存的数据，N - 3因此您可以摆脱它。这在一定程度上减轻了内存负担（但幅度不大）。

代码问题/疑虑

  1. 不要记住不需要的值（见上文）。
  2. Python 对可变默认参数的处理意味着memodict 只创建一次。有关更多详细信息，请参阅此 SO 帖子。这也意味着字典在函数返回后（在内存中）存在......不好。通常不要使用可变的默认参数，除非你有令人信服的理由。
  3. list推导式可能比显式 for 循环快一点。在这种情况下更重要的是，它们更具可读性。
  4. 最后一个更像是一种风格。您正在将1或添加2到递归调用返回的项目的尾部。通常这些元素被添加到头部。

解决方案

相同的算法，但内存和时间效率更高

def stepsdyn_new(N, memo):
    try:
        return memo[N]
    except KeyError:
        l1 = [(1,) + items for items in stepsdyn_new(N - 1, memo)]
        l2 = [(2,) + items for items in stepsdyn_new(N - 2, memo)]
        memo.pop(N - 2)
        memo[N] = l1 + l2
        return memo[N]

注意：我将基本情况作为参数传递，但您可以添加原始if/else如果需要。

返回字符串

def stepsdyn_str(N, memo):
    try:
        return memo[N]
    except KeyError:
        l1 = ['1' + x for x in stepsdyn_str(N - 1, memo)]
        l2 = ['2' + x for x in stepsdyn_str(N - 2, memo)]
        memo.pop(N - 2)
        memo[N] = l1 + l2
        return memo[N]

这将返回一个字符串列表（例如 ['111', '12', '21']）而不是元组列表。因为 python 字符串中的每个字符只使用 1 个字节（而不是列表/元组中的每个元素 8 个字节），这会节省大量内存。可以使用以下代码将结果转换回元组列表（尽管这会导致额外的速度/内存损失）：

[tuple(map(int, tuple(x))) for x in stepsdyn_str(N, {0: [''], 1: ['1']})]

效率

注意：该steps函数是一个非记忆的解决方案（为了完整性而包含在下面）。

速度

|--------------|----------------------------|----------------------------|
|              |           N = 20           |           N = 33           |
|--------------|----------------------------|----------------------------|
| steps        | 47 ms ± 7.34 ms per loop   | 41.2 s ± 1.6 s per loop    |
|--------------|----------------------------|----------------------------|
| stepsdyn     | 10.1 ms ± 1.23 ms per loop | 9.46 s ± 691 ms per loop   |
|--------------|----------------------------|----------------------------|
| stepsdyn_new | 6.74 ms ± 1.03 ms per loop | 7.41 s ± 396 ms per loop   |
|--------------|----------------------------|----------------------------|
| stepsdyn_str | 3.28 ms ± 68.8 µs per loop | 3.67 s ± 121 ms per loop   |
|--------------|----------------------------|----------------------------|

使用获得：

%timeit steps(N)
%timeit stepsdyn(N, memo={})
%timeit stepsdyn_new(N, {0: [()], 1: [(1,)]})
%timeit stepsdyn_str(N, {0: [''], 1: ['1']})

记忆

在评估以下功能时，这些估计值特定于我的 16GB 内存 MBP N=33：

  • steps: 10.8% 最大内存
  • stepsdyn: 22.0% 最大内存
  • stepsdyn_new: 15.7% 最大内存
  • stepsdyn_str: 3.6% 最大内存

非记忆解决方案

def steps(N):
    if N == 0:
        return [()]
    elif N == 1:
        return [(1,)]
    else:
        l1 = [(1,) + items for items in steps(N - 1)]
        l2 = [(2,) + items for items in steps(N - 2)]
        return l1 + l2
于 2018-02-03T18:51:49.790 回答
0

如果您想要一种简洁的方法来计算爬 N 步的方式数量，假设一次只能爬 1 步或 2 步，我们可以实现如下所示：

def f(n):
  a, b = 0, 1

  for i in xrange(n):
    a, b = b, a + b

  return b

输出：

   f(3)
=> 3
   f(5)
=> 8
   f(40)
=> 165580141
   f(120)
=> 8670007398507948658051921L

请注意，结果只是第一个(n + 1)斐波那契数。

于 2018-02-04T19:27:22.180 回答