在使用动态规划算法求最优解时,需要解决的问题之一是“重叠子问题”即递照片中的部分重复计算问题，最近在使用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