在使用动态规划算法求最优解时,需要解决的问题之一是“重叠子问题”即递照片中的部分重复计算问题,最近在使用python实现时遇到一些问题,在些将其总结分享:
此处以“斐波那契数列”的实现为例,通过以下函数的学习理解,有助于你提高对python生成器的认知。
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用。
(1)、常归写法,最简洁易理解,重叠子问题却最严重(n越大,需要复复计算的项越多)
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
(2)、自顶向下,采用带有备忘录功能的写法,对已计算结果做事先存储,计算的时候看之前是否已计算,若有则不再重复计算
注意 or 与 | 的用法,没带括号的|会报错,这个坑要注意。
def assistant_note(lt, n):
if (n == 1) or (n == 2):
return 1
if lt[n] != 0:
return lt[n]
lt[n] = assistant_note(lt, n-1) + assistant_note(lt, n-2)
return lt[n]
def fib_arr(N):
if (N < 1):
return 0
arr = [0] * (N+1)
return assistant_note(arr, N)
(3)、自底向上,参照动态规划算法的思路写
def fib_dp(mx):
if mx < 1:
return 0
elif mx == 1:
return 1
else:
n, a, b = 1, 0, 1
while n < max:
a, b = b, a + b
n += 1
return b
(4)、如果生成整个序列,则用以下带生成器写法可实现
注意:在生成器当中,return已不同于普通函数, 它可以独立成句,作为一个结束标识,后面的内容都不会被返回
def fib_gentor(mx):
if mx < 1:
yield 0
else:
n, a, b = 0, 0, 1
while n < max:
yield b
a, b = b, a + b
n += 1
return