Dynamic Programming

直白的翻成中文就是「動態規劃」通常用在把問題最佳化。還記得之前提到的Divide and Conquer嗎？就是將一個大問題切割成許多小問題，這些小問題的形式與大問題相同，只是內容或參數不同，將小問題解決後，再組合起來成為大問題的解。
然而在運算途中，不斷透過遞迴來處理這些小問題，但這些小問題會不斷的重複處理，浪費許多時間即空間在計算重複的問題，這時候就是使用「動態規劃」的時機了！

Concept

利用陣列或list儲存小問題的解，所以相同的小問題只需計算一次，之後就可以快速從陣列中找尋小問題的解，避免重複大量計算，讓程式計算速度更快。

Fibonacci sequence

def fib_DC(n): #Divide and Conquer
    if n<1:
        return 0
    elif n==1:
        return 1
    else:
        return fib_DC(n-1)+fib_DC(n-2)

def fib_DP(n): #Dynamic Programming
    F=[0]
    if n==1:
        F.append(1) 
    else:
        F.append(1) 
        for i in range(2,n+1):
           F.append(F[i-1]+F[i-2])
    return F[n]
if__name__=='__main__':
    print(fib_DC(30))
    print(fib_DP(30))

def C(m,n):
    if n==0 or m==n:
        return 1
    elif n==1:
        return m
    else:
        return C(m-1,n)+C(m-1,n-1)
def C_DP(m,n):
    if n==0 or m==n:
        return 1
    elif n==1:
        return m
    else:
        return C(m-1,n)+C(m-1,n-1)

大家可以想想看，上面組合數C(m,n)是Divide and Conquer，那用Dynamic Programming可以怎麼寫？