Dynamic Programming 1:入門
簡介
如果你常刷leetcode,會發現許多問題帶有Dynamic Programming的標籤。事實上帶有dp標籤的題目有115道,大部分為中等和難題,佔所有題目的12.8%(2018年9月),是佔比例第二大的問題。
如果能系統地對dp這個topic進行學習,相信會極大地提高解題速度,對今後解決實際問題也有思路上的幫助。
本文以分杆問題為切入點,介紹動態規劃的演算法動機、核心思想和常用的兩種實現方法。
分杆問題
The rod-cutting problem(分杆問題)是動態規劃問題的一個典例。
給出一根長度為n(n為整數)的杆,可以將杆切割為任意份長短不同的杆(其中包含完全不進行切割的情況),每一份的長度都為整數。給出一個整數陣列p[],p[i]表示長度為i的杆的價格,問如何對杆進行切割可以使利潤最大。
p[]陣列的一個示例如下:
思路
在長度為n的杆上進行整數切割,共有 2 n-1 種情況,因為有n-1個點可以選擇是否切割。
將這些可以切割的點編號為1,2,3, ..., n-1,如果先試著在1處切割,則杆變成了長度為1和n-1的兩段;如果試著在2處切割,則杆變為了長度為2和n-2的兩段,以此類推,共有n種切法(包含完全不作切割)。這樣,我們邁出了遞迴的第一步,即把長為n的杆的最優切割分成兩個子問題:長為i的杆的最優切割和長為n-i的杆的最優切割(i = 1,2,...,n)。最終的利潤為兩個子杆的利潤和。
如果用f n 表示長度為n的杆切割後能得到的最大利潤,經過以上分析,我們求取兩個子杆的利潤和的最大值即可。即
f n = max(p n , f 1 + f n-1 , f 2 + f n-2 , ..., f n-1 + f 1 ).
這種思路是正確的,但不是太好,有心人可以注意到子問題之間有較大的重疊之處,比如計算f n-1 時會需要檢視f 1 + f n-2 ,即f 1 + f n-1 這個子問題需要檢視f 1 + f 1 + f n-2 這個切法;而計算f 2 時又需要檢視f 1 + f 1 ,即f 2 + f n-2 這個子問題也會檢視到f 1 + f 1 + f n-2 這個切法,相當於把一些可能性重複查看了多遍。
一個更簡潔合理的思路是:設定左邊這個長為i的杆不可再切割,只有右邊長為n-i的杆可以再切割。則問題變為
f n = max(p i + f n-i ), i = 1,2,...,n
傳統遞迴實現
按照上面的分析,可以初步做一個遞迴實現如下:
1 int cutRod(int n, int[] p){ 2if(n == 0) 3return 0; 4int max = Integer.MIN_VALUE; 5for(int i = 1; i <= n; i++) 6max = Math.max(max, p[i] + cutRod(n - i, p)); 7return max; 8 }
傳統遞迴實現的複雜度
在節點n,演算法的時間複雜度為
T n = 1 + ∑ T i (i = 0,1, ..., n-1)
(其中的1是在節點處做加法和max運算的常數複雜度)
這個式子很好推算,只要將T i 的值以此從後往前代入即可:
T n = 1+T 0 +T 1 + ... +T n-1 = 1+T 0 +T 1 + ... +T n-2 +(1+T 0 +T 1 + ... +T n-2 )
= 2 (1+T 0 +T 1 + ... +T n-2 ) = 2 (1+T 0 +T 1 + ... +T n-3 +(1+T 0 +T 1 + ... +T n-3 ))
= 2 2 (1+T 0 +T 1 + ... +T n-3 ) = ... (總結規律) = 2 n-1 (1 + T 0 )
= 2 n
即傳統遞迴演算法的時間複雜度為 O(2 n ) ,為指數級別。
上一節中說到切割的可能性共有 2 n-1 種,也就是說遞迴演算法會將每種可能性都遍歷到。是否還有優化的可能性呢?
優化
以n = 4為例,畫出遞迴樹結構(節點包含的數字為n的值)
本圖摘自演算法導論(英文版)3rd Ed. 15.1 P346
可以看到子樹之間存在重疊情況。最明顯的是n = 2的子問題和n = 3的子問題呼叫的子樹完全相同,進行了兩遍同樣的計算。而這個子樹中又包含n = 1的子樹,也就是說浪費的幅度是相乘的。
一個優化思路是將每個子問題的計算結果記錄下來,下一次再遇到同樣的問題時直接使用記錄值,這就是動態規劃的核心思想。
動態規劃
如上節所述的,動態規劃是一種“以空間換時間”的思想,適用於 子問題之間存在重疊情況的優化問題 。它的基本思想是將計算過的子問題的答案記錄下來,從而達到每個子問題只計算一次的目的。
動態規劃的實現方法分為top-down和bottom-up兩種,可以理解為前者從遞迴樹的根節點向下遞迴呼叫,而後者從樹的葉結點開始不停地向上迴圈。
top-down with memoization
top-down方法比較容易理解,就是在傳統遞迴的基礎上加入 memoization( 注意與memorization的區 別 。memoization 來自memo,有備忘的意思), 即用陣列或表等結構快取計算結果。在每次遞迴運算時,先判斷想要的結果是否在快取中,如果沒有才進行運算並存入快取。
1 int cutRod(int n, int[] p){ 2int[] memo = new int[n + 1]; 3for(int i = 0; i < memo.length; i++) 4memo[i] = Integer.MIN_VALUE;//initialization 5return cutRod(n, p, memo); 6 } 7 8 int cutRod(int n, int[] p, int[] memo){ 9if(memo[n] != Integer.MIN_VALUE) 10return memo[n];//return value directly if memoized 11if(n == 0) 12return 0; 13int max = Integer.MIN_VALUE; 14for(int i = 1; i <= n; i++) 15max = Math.max(max, p[i] + cutRod(n - i, p, memo)); 16memo[n] = max;//memoize it 17return max; 18 }
bottom-up with tabulation
相比於top-down,bottom-up的特點是使用迴圈而非遞迴,先解決子問題,再利用子問題的答案解決父問題。 tabulation 也很好理解,即用一個表格存放子問題的答案,然後查表獲得父問題需要的所有資訊去解決父問題,解決後也填在表中,直至把表填滿。
事實上,dynamic programming這個令人費解的名字即來源於此。programming在數學界有“列表法”(tabular method)的意思,指的是為了求某函式的最大/最小值,將函式的所有變數的所有可能值列在表中並對錶進行某些操作來獲得結果。在這裡,表格是“靜態”的,每個格子中的資訊是獨立的;而在動態規劃中,表格是“動態”的,一些格子中的資訊依賴於另一些格子中的計算答案。所以,dynamic programming也可以理解為“ 動態列表法 ”,也即此處的tabulation。
top-down的實現如下:
1 int cutRod(int n, int[] p){ 2int[] table = new int[n + 1]; 3for(int j = 1; j <= n; j++){//fill table from j = 1 to n 4int max = Integer.MIN_VALUE; 5for(int i = 1; i <= j; i++) 6max = Math.max(max, p[i] + table[j - i]);//calculate f(j) 7table[j] = max; 8} 9return table[n]; 10 }
複雜度
在bottom-up解法中, 我們從 1至n填入表格,在填入table[j]時,需要查詢table[j-1]到table[0]的所有元素,即要做j次查詢。則填滿表格共要做1+2+3+...+n = O(n 2 )次查詢。則bottom-up解法的時間複雜度為 O(n 2 )。
在top-down解法中,可以這樣分析複雜度:首先由於快取機制,每個子問題只會被計算一次;為了解決大小為n的問題,我們需要計算大小為0,1,2,...,n-1的問題(第15行);計算大小為n的問題又需要n次計算(第14行),因此top-down解法的複雜度也為 O(n 2 )。
實際上,動態規劃將前文圖中的遞迴樹做了簡化,將互相重疊的子樹合併,得到了一個子問題樹。子問題樹中的邊和節點都減少了,意味著時間複雜度得到了優化。
->
概念
看完例子,我們來總結一下動態規劃演算法的相關概念。
Dynamic Programming
- dynamic programming (動態規劃)是一類常用來解決 優化問題 的演算法。它的最大特點是 使用子問題的資訊幫助解決父問題 ,使解題的難度減小。比如,求第1,000,002個斐波那契數這個問題看起來很複雜,但如果已知了第1,000,000和第1,000,001斐波那契數,事情就簡單多了。
- 動態規劃問題有一個顯著的特點,就是 子問題之間存在相互重疊 。動態規劃通過記錄子問題的結果,保證每個子問題只計算一次,減少了時間浪費。動態規劃的時間複雜度通常是多項式複雜度(即O(n k ),k為非負常數),而不記錄結果的演算法由於重複計算,複雜度通常遠高於動態規劃,達到指數複雜度。
- dynamic programming這個英文名詞有些讓人難懂。實際上,這裡的programming不是指程式設計,而是數學上的一種解決優化問題的方法,叫做列表法(tabular method),大致過程是將函式的不同變數值在表中列出並對錶進行各種操作來求得結果。如果列表法是靜態(static)的,則動態規劃演算法中,表格是慢慢增長的,先解決相對簡單的子問題,然後通過子問題的結合求取父問題,這樣表格好像是“動態”的。這就是dynamic programming的意思。
Memoization vs. Tabulation 簡介
- 動態規劃通常有兩種解法: top-down 和 bottom-up 。
- top-down通常以 遞迴 形式出現,從父問題開始,遞迴地求解子問題。top-down的求解過程通常與 memoization 結合,即將計算過的結果快取在陣列或者雜湊表等結構中。當進入遞迴求解問題時,先檢視快取中是否已有結果,如果有則直接返回快取的結果。
- bottom-up通常以 迴圈 形式出現。bottom-up的求解過程通常與 tabulation 結合,即先解最小的子問題,解決後將結果記錄在表格中(通常是一維或二維陣列),解決父問題時直接查表拿到子問題的結果,然後將父問題的結果也填在表中,直到把表格填滿,最後填入的就是起始問題的結果。
參考資料
ofollow,noindex">dynamic programming -- wikipedia
What is dynamic programming? -- Stackoverflow
Tabular Method of Minimisation
Dynamic programming and memoization: bottom-up vs top-down approaches