爬坡步数的动态规划

Question

问题是编写一个函数，用动态规划的方法来爬升N步。考虑到一次只能爬1到2步。在

例如，如果N=3，函数应该返回[（1,1,1），（1,2），（2,1）]。 我用python3编写了一个代码来计算。代码运行得很好，但是当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] 

Answer 1

基本思路

在计算机程序设计中，最基本和最常见的权衡是时间效率和空间效率之间的权衡。回忆录可能对时间有利，但对空间不利，这里就是这样。你的程序崩溃了，因为记忆字典保存了很多数据。马上你的递归关系意味着你永远不需要保存在N - 3点的数据，这样你就可以摆脱它了。这在一定程度上减轻了内存负担（但效果不大）。在

代码问题/问题

1. 不要记住你不需要的价值观（见上文）。在
2. Python对可变默认参数的处理意味着memodict只创建一次。有关详细信息，请参见this SO post。这也意味着字典在函数返回后（在内存中）处于空闲状态。。。不好的。一般不要使用可变的默认参数，除非有令人信服的理由。在
3. list理解可以是a bit faster，而不是显式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。在

返回字符串

^{pr2}$

这将返回一个字符串列表（例如['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']})

内存

在计算N=33的函数时，这些估计值特定于我的16GB内存MBP：

• ^{cd8>最大内存
• 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

Answer 2

如果你想用一种简洁的方法来计算N个台阶的数量，考虑到一次只能爬1步或2步，我们可以这样做：

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

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

  return b

输出：

^{pr2}$

注意，结果只是(n + 1)第Fibonacci个数。在