前言
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 | FibRecurs(n) |
F(n) = F(n-1) + F(n-2)
以F(6)為例子,Top-Down的方式,會重複計算已經計算過的值
1 | F(6) = F(5) + F(4) |
F(6)用到的F(5)同時也連鎖了F(4)與F(3),而F(4)又連鎖下去…..
所以費波納契數列用遞迴的複雜度是O(2^n)
費波納契數列的用遞迴做的話,每次累加數值都使用同一塊記憶體,n太大的話就會oveflow,是危險的作法
DP做法
1 | FibList(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元的硬幣