淺談Dynamic Programming

Posted on

Dynamic Programming(DP) 能帶來的好處是降低時間複雜度，用空間換取時間。

Recursion

一個常見的recursion例子即是費波那契數（Fibonacci number），下方是用recursion來實作的C++
程式：

1
2
3
4
5
6
int fib(n){
    if(n<=1)
        return n
    else
        return fib(n-1)+fib(n-2)
}

上方的程式可以藉由下方的樹狀圖表示，這樣透過top-down的方式來解會重複計算數列中的值，大幅增加了計算時間。這樣的方法的時間複雜度為$O(n^2)$，但空間複雜度為$O(1)$。

Dynamic programming(DP)

DP用空間換取時間，它不進行重複的運算，是透過bottom-up的方式將表格建出，也就是依序算出數列中的值，並將計算完的值都儲存起來以供後續查表使用，避免重複計算。

1
2
3
4
5
6
7
8
int fib (n) {
    Fib[0] = 0;
    Fib[1] = 1;
for (int i = 2; i<=n; i++){
    Fib[i] = Fib[i-1] + Fib[i-2];
}
       return Fib[n]
    }

因為計算完的值都會被儲存起來，這樣的方法比
recursion需要更多的記憶體。避免重複計算使得時間複雜度變為$O(n)$，儲存計算完的值使得空間
複雜度為$O(n)$。

DP的4個步驟

Step-1 觀察並找出答案的特徵與結構。e.g.觀察費波那契數為前一個數字以及後一個數字的和。
Step-2 以遞迴方式定義函數。e.g. fib(n)=fib(n-1)+fib(n-2); BC: fib(0)=0, fib(1)=1。
Step-3 建表，用bottom-up的方式依序求解。e.g.

Step-4 利用表格資訊組合出答案。