最简洁易理解的写法效率不一定高--斐波那契数列-python解决动态规划中的重叠子问题

时间:2024-01-27 20:16:40

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