初學動態規劃

05-01

講道理，我對dp這塊的理解並不深，當初學的時候，也僅僅停留在一些名詞上。比如大佬們經常說的數位dp，樹形dp，區間dp，插頭dp，棋盤dp，背包dp等等。。。

那究竟什麼是dp呢?維基百科上是這樣定義的：

DP就是一種方法，該方法能夠將複雜的問題分解成為一系列簡單的子問題。

時隔一段時間了，準備好好把dp這個演算法總結總結，不會的地方抓緊補上，會的地方夯實夯實，寫出一些自己不一樣的見解，爭取在每天的積累中，能夠不斷的進步。

在介紹DP之前，我們還是先來看看什麼是遞推，什麼是遞歸？因為，我覺得，要想把dp的問題做好，必須對於遞推和遞歸的理解夠深入，這樣才能在後續理解dp的過程中，遊刃有餘。

從一道題目講起

先從上樓梯問題1來說：

每次只能上1個台階，或者兩個台階。求上到第n節台階的總的方法數是多少？

這個問題，先從最原始的想法開始。

如果我們正著開始想。

當n=1時，只有1種方法

當n=2時，有2種方法

當n=3時，有3種方法

當n=4時，有5種方法

。。。

當n=k時候，聰明的讀者可能會總結出規律來，答案為f(k-1)+f(k-2)

但是，如果你對於這些數字不敏感的話，有可能不能得出這個結論。這個時候，我們不妨把問題的角度轉換下。比如說，我們從最後一節台階來開始，倒著考慮問題。假如說我們站在最後一節台階，那麼怎麼樣才能達到最後一節台階呢？

從倒數第二層，一次性上兩節台階到達最後一層
從倒數第一層，一次性上一節台階到達最後一層

令最後一層台階是n，這樣，到達最後一節的方法數就是f(n) = f(n-1)+f(n-2)了。

然後，我們倒著推問題，最後就得到了一個邊界條件,f(1)=1, f(2) = 2

那麼無論n（n>=1）取多少，我們都可以得到最終的解。

關於f(n-1)和f(n-2)我們把它定義為最優子結構

f(1)=1, f(2) = 2定義為邊界

f(n) = f(n-1)+f(n-2)定義為狀態轉移方程

這三個概念是所有dp問題中所包含的最重要的概念。我們必須要好好吃透它，關於這三個概念的定義和使用，下面的問題還會多次出現，如果不是很懂，不要緊，耐住性子，繼續往下讀就行了。

到這裡，我們就能夠寫出來這個問題的遞歸求解過程

int fun( int step ) { if ( step < 1 ) return 0; if ( step == 1 ) return 1; if ( step == 2 ) return 2; else return fun(step-1)+fun(step-2);}

是不是感覺我們已經把這個題目完美的解決了呢？我們再來分析下這個問題的時間複雜度和空間複雜度各是多少。

可以看出，時間複雜度是O(2^n),空間複雜度也是O(n)。

時間複雜度太高了，發現問題了嗎?其實，在我們每次遞歸的過程中，都會有重複計算的部分。比如說，f(8) = f(7)+f(6) ， f(7) = f(6)+f(5),但是當我們計算f(7)的時候，需要f(6)。

計算f(8)的時候也需要計算f(6)。這兩個是同一個f(6)。故，只需計算一次就行了。

那麼，我們就針對這個問題引入一個新的東西，叫做記憶化數組。

記憶化數組的作用就是干這樣的事情的，使得那些需要重複計算過的部分僅僅計算一次，儘快的求出問題的解。類似hash的思想，來暫存計算結果。

實現代碼如下：

int memory[MAX]={0};int fun( int step ) { if ( memory[step]!=0 ) return memory[step]; if ( step<1 ) return 0; if ( step==1 ) return 1; if ( step==2 ) return 2; else return memory[step] = fun(step-1)+fun(step-2);}

再來分析下時間複雜度和空間複雜度各為多少？

首先，時間複雜度就是O(n)，空間複雜度也為O(n)

其實，做到這一步實際上就可以了，時間上已經是最快的了，你要是還想把空間複雜度再變低一些，那就是優化到O（1）。這個可以藉助我們先前學過的斐波那契數列的循環式寫法來做。

int fun( int step ) { if ( step < 1 ) return 0; if ( step == 1 ) return 1; if ( step == 2 ) return 2; int a = 1; int b = 2; int temp = 0; for ( int i = 3;i <= step;i++ ) { temp = a+b; a = b; b = temp; } return temp;}

這個爬樓梯問題，我們已經解決的非常好了，那麼接下來，我們再來將問題進一步的加強。

上樓梯問題2：

每次爬樓梯時，可以往上爬不超過4節( 1,2,3,4 )
求爬上N節樓梯的不同方案數

還是和剛剛的問題求解思路一樣，我們從最後一步開始看問題。

f(n) = f(n-1)+f(n-2)+f(n-3)+f(n-4)

當n=4時，f(4) = f(3)+f(2)+f(1)+f(0)

那麼，通過手算，我們得到f(1) = 1, f(2) = 2, f(3) = 4, f(4) = 8

這樣來看f(0) = 8-4-2-1 = 1

所以，我們就得到了上樓梯問題2的最優子結構，邊界，狀態轉移方程，該問題就順利解決了。代碼如下

int fun( int step ) { if ( step==0 ) return 1; if ( step==1 ) return 1; if ( step==2 ) return 2; if ( step==3 ) return 4; return f(step-1)+f(step-2)+f(step-3)+f(step-4);}

上樓梯問題3：

當我們把每次可以往上爬的台階數規定為不超過n的時候。
那麼，求上到第n節台階所需要的方法數。

如果還是用前面的最優那個O(n)的方法，當n趨向特別大的時候，該方法顯然不成立。

那麼，我們就可以通過使用矩陣乘法+快速冪的方法把問題降低到O(logn)的複雜度。

$[f(1),f(0)][1 1; 1 0 ]^{n-1} = [f(n),f(n-1)]$

通過矩陣快速冪，就能達到O(logn)的複雜度

遞歸：

什麼是遞歸呢？我對於遞歸的理解就是一個自己調用自己的過程，但是往往遞歸的過程中，必須要明確遞歸終止的條件是什麼，如果你不知道遞歸終止的條件，那麼就會導致棧溢出的問題。

和很多講演算法的書一樣，講解遞歸的時候，一開始給大家介紹的也是「漢諾塔」問題。

漢諾塔問題其實可以被拆分成三個步驟子問題來思考：

第一個步驟子問題：首先將A柱子上的前n-1個盤子，藉助C柱子，移動到B柱子上

第二個步驟子問題：然後將A柱子上的第n個盤子，直接移動到C柱子上

第三個步驟子問題：將B柱子上的前n-1個盤子，藉助A柱子，移動到C柱子上。

如果按照次序執行上述步驟子問題，我們就能得到最終問題的解。細心的讀者可能會發現，第一個步驟子問題和第三個步驟子問題的本質是一樣的，只不過方法所應對的參數有所不同。那這個時候遞歸就可以起到作用了。解決的代碼如下所示：

# include <cstdio># include <iostream>using namespace std;int step;void move( int n, char a,char c ){ printf("the %d %c->%c ",n,a,c );}void hanuota(int n,char a,char b ,char c){ step++; if ( n==1 ) { move(1,a,c); return; } else { hanuota(n-1,a,c,b); move(n,a,c); hanuota(n-1,b,a,c); }}int main(void){ char a = A; char b = B; char c = C; int n = 3; hanuota(n,a,b,c); cout<<step<<endl; return 0;}

有了遞推和遞歸的基礎，我們接下來，就來做做幾道經典的dp問題吧。

1-dimensional DP Example

Problem : given n, find the number of different ways to write n as the sum of 1,3,4
Example : for n = 5, the answer is 6

哈哈哈，是不是感覺非常的easy？沒錯，這就是剛剛我們一開始講的上樓梯題目的變形，只不過，這次的樓梯必須是一次上1節，或者一次上3節，或者一次上4節。

最優子問題就是：f(n-1),f(n-3),f(n-4)
邊界條件就是：f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 4
狀態轉移方程：f(n) = f(n-1)+f(n-3)+f(n-4)，當n=4時，推出f(0) = 1

代碼如下：

# include <cstdio># include <iostream>using namespace std;# define MAX 12345int f[MAX];int main(void){ f[0] = f[1] = f[2] = 1; f[3] = 2; int n; cin>>n; for ( int i = 4;i <= n;i++ ) { f[i] = f[i-1]+f[i-3]+f[i-4]; } cout<<f[n]<<endl; return 0;}

時間複雜度為O(n)，當n非常大的時候，考慮使用矩陣快速冪，將時間複雜度變成O(logn)

再來一個經典的例子，POJ 2663 Tri Tiling

Problem：Given n , find the number of ways to fill a 3*n board with dominoes

這道題，其實也是1-dimensional 的dp問題，我們知道，該矩形的寬恆定為3.

那麼，當我們每次增加一個長度為2的矩形的時候，會得到三種情況的矩形

第一種情況

第二種情況就是將第一種情況順時針旋轉180°即可

第三種情況

那麼得到一個部分子問題為3*f(n-2)

當我們每次增加一個長度為4的矩形的時候，我們又會得到兩種情況

第一種情況

第二種情況，還是把第一種情況旋轉180°

那麼，我們又得到一個部分子問題為2*f(n-4)

以此類推，我們得到2*f(n-6)+...+2*f(0)

最終得到f(n) = 3*f(n-2)+2*f(n-4)+2*f(n-6)+...+2*f(0)

寫出f(n-2) = 3*f(n-4)+2*f(n-6)+...+2*f(0)

上面的式子減去下面的式子，我們得到

f(n)-f(n-2) = 3*f(n-2)-f(n-4)

f(n) = 4*f(n-2)-f(n-4)

這個時候，就得到了狀態轉移方程。

邊界條件f(0)=1,f(2) = 3

代碼實現如下：

# include <cstdio># include <iostream>using namespace std;# define MAX 123typedef long long LL;int f[MAX];int main(void){ f[0] = 1; f[2] = 3; for ( int i = 4;i <= 30;i++ ) { f[i] = 4*f[i-2]-f[i-4]; } int n; while ( scanf("%d",&n) ) { if (n==-1) break; if (n%2==1) printf("0 "); else { printf("%d ",f[n]); } } return 0;}

2-dimensional DP Example

Problem: given two strings x and y, find the longest common subsequence (LCS) and print its length
Example:

x: ABCBDAB
y: BDCABC
BCAB is the longest subsequence found in both sequences, so the answer is 4

LCS問題，屬於DP的經典問題了，再次拿來細細品味，還是能感覺到其中每個點背後的精髓的。

這個問題，就不能再通過f[i]這種一維的形式來定義了，因為它要分別維護兩個字元串x,y

並且x和y的變化也並不是完全保持一致的，此時，就需要藉助2-dimensional DP幫助了。

以每個字元為突破口，當x[i]==y[j]的時候，f[i][j] = f[i-1][j-1]+1

f[i][j]表示的是以x[i]結尾，y[j]結尾的最長公共子串的長度。

當x[i]!=y[j]的時候，f[i][j] = max(f[i-1][j],f[i][j-1])

最終的狀態轉移方程:f[i][j] = max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+1)

邊界條件 f[i][0] = 0, f[0][j] = 0

代碼實現如下：

# include <cstdio># include <iostream># include <cstring>using namespace std;# define MAX 123int f[MAX][MAX];char str1[MAX],str2[MAX];char str11[MAX],str22[MAX];int main(void){ scanf("%s",str1); for ( int i = 0;i < strlen(str1);i++ ) { str11[i] = str1[i+1]; } scanf("%s",str2); for ( int j = 0;j < strlen(str2);j++ ) { str22[j] = str2[j+1]; } for ( int i = 0;i <= strlen(str1);i++ ) f[i][0] = 0; for ( int j = 0;j <= strlen(str2);j++ ) f[0][j] = 0; for ( int i = 1;i <= strlen(str1);i++ ) { for ( int j = 1;j <= strlen(str2);j++ ) { if ( str1[i]==str2[j] ) { f[i][j] = f[i-1][j-1]+1; } else { f[i][j] = max(f[i-1][j],f[i][j-1]); } } } printf("%d ",f[strlen(str1)][strlen(str2)]); return 0;}

有了最長公共子串（LCS）的基礎，我們再來看一道經典的題目。

Problem：given a string x = x1,x2,..,xn. find the minimum number of characters that need to be inserted to make it a palindrome

就是說，給你一個字元串，問給這個字元串最少添加多少個字元，使得這個字元串變成一個迴文串。

對於這個問題，看看你能不能通過剛剛講的LCS作為媒介來解決？

其實仔細想想真的不難，我現在來講講我首先拿到這個題目後的想法和解決手段吧。

首先，題目的目的是要求我們最終得到一個迴文串。那麼迴文串的性質就是正著讀和反著讀都是一樣的字元串
有了這個性質，我們只要看看原來字元串的連續子串中有哪些連續子串是迴文的，這個問題就能解決了。
因為我們只要找到了原串的最長迴文子串，那麼用總的長度減去這個最長的迴文子串的長度，就是我們需要添加的最小字元的個數
針對這個問題，有兩種方法：

第一種方法：直接求原串和反轉後的串的LCS，然後用總的長度減去LCS的長度就是需要添加的最小字元的個數
第二種方法：定義f[i][j]表示以str[i]為首的，str[j]為結尾的字元需要添加f[i][j]個字元才能使得str[i]到str[j]組成的字元串是迴文串。那麼狀態轉移方程就是：當str[i]==str[j]的時候，f[i][j] = f[i+1][j-1]。當str[i]!=str[j]的時候，f[i][j] = min(f[i+1][j],f[i][j-1])+1

第一種方法代碼實現：

# include <cstdio># include <iostream># include <cstring>using namespace std;# define MAX 123int f[MAX][MAX];char str1[MAX],str2[MAX];char str11[MAX],str22[MAX];int main(void){ scanf("%s",str1); int len = strlen(str1); for ( int i = 0;i < len;i++ ) { str2[i] = str1[len-i-1]; } for ( int i = 0;i < len;i++ ) { str11[i+1] = str1[i]; } for ( int i = 0;i < len;i++ ) { str22[i+1] = str2[i]; } for ( int i = 0;i <= len;i++ ) f[i][0] = 0; for ( int j = 0;j <= len;j++ ) f[0][j] = 0; for ( int i = 1;i <= len;i++ ) { for ( int j = 1;j <= len;j++ ) { if ( str11[i]==str22[j] ) { f[i][j] = f[i-1][j-1]+1; } else { f[i][j] = max(f[i-1][j],f[i][j-1]); } } } cout<<len-f[len][len]<<endl; return 0;}

第二種方法代碼：

# include <cstdio># include <iostream># include <cstring>using namespace std;# define MAX 123int f[MAX][MAX];char str1[MAX],str2[MAX];char str11[MAX],str22[MAX];int main(void){ scanf("%s",str1+1); int len = 0; for ( int i = 1;str1[i];i++ ) { len++; } for ( int i = 1;i <= len;i++ ) f[i][i-1] = f[i][i] = 0; for ( int t = 2;t <= len;t++ ) { for ( int i = 1, j = t;j <= len;i++,j++ ) { if ( str1[i]==str1[j] ) { f[i][j] = f[i+1][j-1]; } else { f[i][j] = min(f[i+1][j],f[i][j-1])+1; } } } cout<<f[1][len]<<endl; return 0;}

解決了這幾道經典的dp問題，大家有沒有dp建立一個似懂非懂的感覺？只要這種感覺有就行了，對於很多的dp初學者，都是急著想弄清楚dp到底是什麼？在我看來，與其著急去涉及dp的形式化概念，不如先把遞推和遞歸以及dp的本質是什麼理解清楚。當然dp的內容還有很多，後面我會在開文章來慢慢講各種類型的dp，所以，大家不要急。

總結：

dp：就是大事化小，小事化了。
dp的三個重要因素：

最優子結構
邊界條件
動態轉移方程