iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
0

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可以怎麼寫?


上一篇
[Day26] init and self
下一篇
[Day28] 實例演練Leetcode239
系列文
從0開始學習程式-Python32

尚未有邦友留言

立即登入留言