前言

DP 這個名詞乍看之下會有點誤會它的意思,其實在寫一些處理陣列的程式中已經不知不覺使用了 DP,我覺得 DP 比較像是一種概念而非技術,難的也不是 DP 本身,而是要如何設計用 DP 能達成的演算法去儲存與計算資料

概念

動態規劃是基於 Recurrence 的條件下的一種概念(不是 Recursive 喔)

DP 跟遞迴的共通點就是每次都是用一樣的規則去計算東西,每次計算的結果會 depend 在前一次的結果,但是DP每次的計算結果是根據前面的表格已經儲存好來的結果來計算,屬於 Bottom-up 的方式

遞迴是將東西存在同一塊記憶體,會一直 call back,是屬於 Top-Down 的方式,所以當要處理的資料不是收斂的計算方式(不會越變越小,資料值越來越大的話),遞迴的效率就會非常差且可能會產生 overflow

Dynamic Programming 把計算結果存到表格,不需要重覆計算

在Dynamic Programming中,將問題拆解成子問題(sub-problem)是最重要的一環 (跟遞迴一樣)

舉一個理解 DP 跟遞迴不同的例子

費波納契數列 (Fibonacci number)

遞迴做法

1
2
3
4
5
FibRecurs(n)
if n<=1:
return n
else:
return FibRecurs(n-1) + FibRecurs(n-2)

F(n) = F(n-1) + F(n-2)

以F(6)為例子,Top-Down的方式,會重複計算已經計算過的值

1
2
3
4
5
6
F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) => ending

F(6)用到的F(5)同時也連鎖了F(4)與F(3),而F(4)又連鎖下去…..

所以費波納契數列用遞迴的複雜度是O(2^n)

費波納契數列的用遞迴做的話,每次累加數值都使用同一塊記憶體,n太大的話就會oveflow,是危險的作法

DP做法

1
2
3
4
5
6
7
FibList(n)
create an array F[0..n]
F[0] ← 0
F[1] ← 1
for i from 2 to n:
F[i] ← F[i-1] + F[i-2]
return F[n]

可以發現複雜度遠小於遞迴,是O(n),且記憶體較不會有overflow的問題

第二種方式就是開一個陣列,把每次n的計算結果都存到對應的表格,費波納契的特性就是利用前兩個數值相加,所以滿直觀就能想到

DP跟Greedy也很像,但是Greedy每次都是假設某一種條件就是最佳解然後不斷往下搜尋,DP則是要考慮現有的全部條件,因為有些情況下,每次取最大值並不一定是最佳解

經典的換錢問題通常都會直覺用Greedy去解決,但是也有例外的可能

比如硬幣額度有(1, 8, 10)的情況下,24元最少用幾枚硬幣能湊成?

Greedy
: 會優先考慮最大額度10,湊成24的可能就會是2個10元和4個1元,總共6枚
6枚在這個問題之下並不是最佳解,最佳解是3個8元,3枚硬幣

這種例外顯示出Greedy的缺點,不能考慮所有問題,所以要用DP的方式去解決

換錢問題

硬幣額度(1, 8, 10),16元的情況

根據要換多少錢,開相對應的1維陣列

M[17] (0~16),一開始初始都為0,從M[0]開始填格子

每次填格子都考慮前面格子的錢(index)與存放的值(硬幣數量)

  • M[0]:湊0元的情況就是0,填入0
  • M[1]:湊1元的情況就是M[0] + 1,填入1
  • M[2]:湊2元的情況是M[1] + 1,填入2

如何動態規劃

以實作的觀點來拆解:

M[3]
考慮3種幣值,以目前的index = 3,減去這3種幣值得到前面各種金錢值下的硬幣數量,比較哪一個最小,可以先捨去不可能的情況

  • M[3-1] + 1 = 3
  • M[3-8], index <=0, 不可能
  • M[3-10], index <=0, 不可能

… 以此類推到M[8]就會有比較值發生了

M[8]
湊8元的情況就需要考慮兩種情形

  • M[8-1] + 1 = 8 (8元-1元的意思就是7元可以加1元得到8元)
  • M[8-8] + 1 = 1 (8元-8元的意思就是0元可以加8元得到8元)
  • M[8-10], index <= 0, 不可能

M[8] = min(M[8-1] + 1, M[8-8]+1) = 1

如此一直填下去,就能填到M[16] = 2,就是最終的最佳解了

再將以上的拆解推演寫成程式碼並不難

DP 有一個重要的特色就是可以透過 Backtrack 從表格最後面往前推算最佳解的組成

以上述的換錢問題來說,填完陣列後M[16] = 2

可以從M[16]往前紀錄,因為已知M[16] = 2,所以他的最佳解組成可以開一個A[2]陣列,或是用vector陣列一個一個push_back

找尋M[16-幣值] = M[16] - 1,記錄下這個index

  • M[16-1], M[16-8], M[16-10]這三個做判斷,會找到M[16-8] = M[16] - 1
  • 紀錄index為 16-8 = 8,紀錄幣值到A[0] = 8
  • 找尋M[8-幣值] = M[8] - 1,就會找到M[8-8]符合,記錄這個index,記錄幣值到A[1] = 8
  • 當index = 0時就結束,此時A陣列也記錄完了,A = [8, 8]

所以最佳解的組成就是2枚8元的硬幣