最簡潔易了解的寫法效率不一定高--斐波那契數列-python解決動态規劃中的重疊子問題

     在使用動态規劃算法求最優解時,需要解決的問題之一是“重疊子問題”即遞照片中的部分重複計算問題，最近在使用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