爬楼梯方式数的动态规划
Dynamic Programming for the number of ways of climbing steps
题目是用动态规划写一个函数求爬N步的方法数。鉴于一次只能爬1个台阶或2个台阶。
例如,如果 N=3,函数应该 return [(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]
基本思路
在计算机编程中,最基本和最常见的权衡是时间效率和 space 效率之间的权衡。记忆化对时间有好处,但对 space 不利,这里就是这种情况。您的程序正在崩溃,因为该记忆字典包含大量数据。马上你的循环关系意味着你永远不需要保存在 N - 3
点的数据,所以你可以摆脱它。这在一定程度上减轻了内存负担(但幅度不大)。
Problems/concerns 代码
- 不要记住不需要的值(见上文)。
- Python 对可变默认参数的处理意味着
memo
dict 只创建一次。有关详细信息,请参阅 this SO post。这也意味着字典在函数 returns 之后(在内存中)...不好。通常不要使用可变的默认参数,除非你有令人信服的理由。
list
理解可以比显式 for 循环 a bit faster。更重要的是,在这种情况下,它们更具可读性。
- 最后一个更像是一种风格。您正在将
1
或 2
添加到从递归调用 returned 的项目的尾部。通常这些元素被添加在头部。
解决方案
相同的算法,但内存和时间效率更高
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]
这将 return 字符串列表(例如 ['111', '12', '21'])而不是元组列表。因为 python 字符串中的每个字符仅使用 1 个字节(而不是 list/tuple 中每个元素使用 8 个字节),这会节省大量内存。可以使用以下代码将结果转换回元组列表(尽管这会产生额外的 speed/memory 惩罚):
[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
如果您想要一种简洁的方式来计算攀登 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)
个 Fibonacci 数字。
题目是用动态规划写一个函数求爬N步的方法数。鉴于一次只能爬1个台阶或2个台阶。
例如,如果 N=3,函数应该 return [(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]
基本思路
在计算机编程中,最基本和最常见的权衡是时间效率和 space 效率之间的权衡。记忆化对时间有好处,但对 space 不利,这里就是这种情况。您的程序正在崩溃,因为该记忆字典包含大量数据。马上你的循环关系意味着你永远不需要保存在 N - 3
点的数据,所以你可以摆脱它。这在一定程度上减轻了内存负担(但幅度不大)。
Problems/concerns 代码
- 不要记住不需要的值(见上文)。
- Python 对可变默认参数的处理意味着
memo
dict 只创建一次。有关详细信息,请参阅 this SO post。这也意味着字典在函数 returns 之后(在内存中)...不好。通常不要使用可变的默认参数,除非你有令人信服的理由。 list
理解可以比显式 for 循环 a bit faster。更重要的是,在这种情况下,它们更具可读性。- 最后一个更像是一种风格。您正在将
1
或2
添加到从递归调用 returned 的项目的尾部。通常这些元素被添加在头部。
解决方案
相同的算法,但内存和时间效率更高
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]
这将 return 字符串列表(例如 ['111', '12', '21'])而不是元组列表。因为 python 字符串中的每个字符仅使用 1 个字节(而不是 list/tuple 中每个元素使用 8 个字节),这会节省大量内存。可以使用以下代码将结果转换回元组列表(尽管这会产生额外的 speed/memory 惩罚):
[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
如果您想要一种简洁的方式来计算攀登 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)
个 Fibonacci 数字。