Dynamic Programming

中譯「動態規劃」。英文常常縮寫成DP。

dynamic是指「動態」的意思。programming在數學領域是指「最佳化（optimization）」，例如求極大值、求極小值。

顧名思義，DP是一個以動態的方式來進行最佳化的方法。

DP = Divide and Conquer + Memoization

DP可視做是Divide and Conquer的延伸版本。當遞迴分割出來的問題，一而再、再而三出現──就運用Memoization儲存全部問題的答案，避免重複求解，以空間來換取時間。

由於Divide and Conquer是以小問題來求出大問題，又由於全部問題的答案都儲存在記憶體的緣故，因此計算答案的過程，就是反覆不斷地在各塊記憶體中讀取數據、計算數據、儲存數據，動感地達成最佳化──動態規劃之名由此而來。

DP的精神，就是建立一個表格，紀錄計算過程當中的所有數值。反覆利用目前算好的問題，求出還沒算好的問題。

出現過的問題會被儲存

算好原問題之後，也一併算好了所有出現過的問題，其答案都可直接從表格存取。

時間複雜度、空間複雜度

問題的答案都在表格中。記憶體足夠的情況下，存取一個問題的答案通常只需O(1)。如果一個問題可以分成O(d)個子問題（一個問題的答案需要由O(d)個更小的問題計算而得），而全部的子問題共有O(n)個，時間複雜度就是O(n * d * 1)。

空間複雜度則必須以子問題們的出現期間來決定。在計算過程當中，不再用於計算的子問題，就不必再儲存於表格中，記憶體就可以釋放，或者回收再利用，整體的空間複雜度就會降低。若只是單純的要儲存全部子問題，空間複雜度就是O(n)。

範例：階乘（Factorial）

求得N階乘，也就是N!，也就是1 × 2 × 3 × ⋯ × N，也就是1到N的連乘積。

時間複雜度：每個問題依賴一個小一號的問題，也就是每個問題用O(1)時間就可算得。共有N個問題，所以算出所有問題要用O(N)時間。

簡單來說，1乘到N，乘了N-1次，故時間複雜度是O(N)。

空間複雜度：共有N個問題，所以要用O(N)空間。如果不需要紀錄全部問題的答案，只想計算一個特定問題的答案，那只需要一個變數就可以了，也就是O(1)空間。

簡單來說，1!到N!都要儲存的話，共有N個值，建立一條N格的陣列來儲存，故空間複雜度是O(N)。如果只想算出N!，那麼用一個變數累積乘積就夠了，故空間複雜度是O(1)。

UVa 623 568 10220 10323

範例：巴斯卡三角形（Pascal's Triangle）

時間複雜度為O(N^2)，空間複雜度為O(N^2)。

巴斯卡三角形左右對稱，可以精簡掉對稱部分。巴斯卡三角形逆時針轉45˚，視覺上就可以一一對應至表格。

UVa 369 485 10564

DP ≈ State Space Search

有人會把DP類比為State Space Search：「問題」改稱「狀態」、「全部問題」改稱「狀態空間」、「遞迴公式」改稱「狀態轉移函式」。

由於觀念上確有雷同之處，於是造就這種說法。

用Dynamic Programming設計演算法時的步驟

1. 利用Divide and Conquer把原問題遞迴地分成許多更小的問題。（recurrence）
   1-1. 子問題與原問題的求解方式皆類似。（optimal sub-structure）
   1-2. 子問題會一而再、再而三的出現。（overlapping sub-problems）
2. 設計計算過程：
   2-1. 確認每個問題需要哪些子問題來計算答案。（recurrence）
   2-2. 確認總共有哪些問題。（state space）
   2-3. 把問題一一對應到表格。（lookup table）
   2-4. 決定問題的計算順序。（computational sequence）
   2-5. 確認初始值、計算範圍。（initial states / boundary）
3. 實作程式，主要有兩種方式：
   3-1. Top-down, Recursive.
   3-2. Bottom-up, Iterative.

總結

現在已經有許多問題已經發掘出DP的解法，這些問題通常以遞迴公式和表格結構的樣式，做為主要的分類依據。有賴前人辛苦耕耘，近年來已漸漸整理出幾個經典的題型了。學習這些題型，可以增廣解題的思考方向。大家在學習之餘，也不妨順便開創一些新題型，可供後人學習！

一、recurrence

以下以著名的爬樓梯問題做為範例。遞迴公式如下：

f(n) =
 { 1                 , if n = 1
 { 2                 , if n = 2
 { f(n-1) + f(n-2)   , if n >= 3

二、state space

當要計算第五階的爬法種類數目，乍看之下會使用到「爬完一階」、「爬完二階」、「爬完三階」、「爬完四階」、「爬完五階」總共五種問題的答案。

而「爬完零階」、「爬完負一階」、「爬完負二階」以及「爬完六階」、「爬完七階」都是不存在的答案，沒有必要計算。

三、lookup table

我們可以建立六格的陣列，儲存全部問題的答案，每一格都都對應到一個問題的答案。表格的第零格不使用，第一格對應到「爬完一階」的答案，第二格對應到「爬完二階」的答案，以此類推。

如果只想要求得特定一個問題的答案，那麼僅需兩個變數紀錄才剛算過的問題的答案。

四、computational sequence

由遞迴公式可知，每個問題都必須依賴階數少一階、階數少二階這兩個子問題，所以必須由階數較小的子問題開始算。

計算順序是：「爬完一階」的答案、「爬完二階」的答案、……、「爬完五階」的答案。

五、initial states / boundary

必須最先計算的問題是「爬完一階」與「爬完二階」，必須在程式中內建答案，填入表格之中，才能進而計算其他問題。用心算方式求得「爬完一階」的答案是1，「爬完二階」的答案是2。

必須最後計算的問題是原問題「爬完五階」。

為了讓表格看起來更順暢、為了讓程式碼比較好寫，可以加入「爬完零階」的答案，對應到表格的第零格。「爬完零階」的答案，可以使用「爬完一階」的答案與「爬完兩階」的答案，刻意逆推而得。

UVa 11069

最後可以把初始值、尚待計算的部份、不需計算的部分，統整成一個遞迴公式：

f(n) =
 { 0                 , if n < 0               [Exterior]
 { 1                 , if n = 0               [Initial]
 { 1                 , if n = 1               [Initial]
 { f(n-1) + f(n-2)   , if n >= 2 and n <= 5   [Compute]
 { 0                 , if n > 5               [Exterior]

實作程式

直接用遞迴實作，而不使用記憶體儲存各個問題的答案，是最直接的方式，也是最慢的方式。時間複雜度是O(f(n))。有些問題一而再、再而三的出現，不斷呼叫同樣的函式，效率不彰。很多剛接觸DP的新手都會犯這種錯誤。

int f(int n) { if (n == 0 || n == 1) return 1; else return f(n-1) + f(n-2); }

正確的DP，是一邊計算，一邊將計算出來的數值存入表格當中，以後便不必再重算。這裡整理了兩種實作方式：

1. Top-down, Recursive.
2. Bottom-up, Iterative.

這兩種方式各有優缺點，以下說明這兩種方式有何不同。

實作程式：Top-down, Recursive

第一種。採用Divide and Conquer的遞迴實作方式，以Divide階段分割原問題，並以Merge階段來計算出原問題的答案。每當計算出一個問題的答案後，就馬上儲存在表格裡面，並紀錄該問題已計算。

int table[6]; // 表格，儲存全部問題的答案。 bool solve[6]; // 記錄問題是否已計算 int f(int n) { if (n == 0 || n == 1) return 1; if (solve[n]) return table[n]; table[n] = f(n-1) + f(n-2); // 將答案存入表格 solve[n] = true; // 紀錄已計算 return table[n]; } void stairs_climbing() { // initial for (int i=0; i<=5; i++) solve[i] = false; // compute cout << "爬完五階的踏法有" << f(5) << "種"; int n; while (cin >> n && (n >= 0 && n <= 5)) { cout << "爬完" << n << "階的踏法" << "有" << f(n) << "種"; } } // 有時候可以將solve陣列跟table合併，將程式碼簡化。 int table[6]; int f(int n) { if (n == 0 || n == 1) return 1; // if (table[n] != 0) // 直接用 0 來代表沒算過 if (!table[n]) // 解讀成：如果還沒填。 return table[n]; return table[n] = f(n-1) + f(n-2); } void stairs_climbing() { // initial for (int i=0; i<=5; i++) table[i] = 0; // compute cout << "爬完五階的踏法有" << f(5) << "種"; }

這個方式的好處是不必斤斤計較計算順序，因為程式碼中的遞迴結構會迫使最小的問題先被計算。這個方式的另一個好處是只計算必要的問題，而不必計算所有可能的問題（計算整個狀態空間）。

這個方式的壞處是程式碼採用遞迴結構，不斷呼叫函式，執行效率較差。這個方式的另一個壞處是無法自由地控制計算順序，因而無法妥善運用記憶體，浪費了可回收再利用的記憶體。

UVa 10446 10520

實作程式：Bottom-up, Iterative

第二種。訂定一個計算順序，然後由最小的問題開始計算，其特色是程式碼通常只有幾個迴圈。這個方式的好處與壞處恰與前一個方式互補。

首先建立表格。

int table[6]; int table[5 + 1];

人工心算出「爬完零階」的答案、「爬完一階」的答案，填入表格當中，作為初始值。分別填到表格的第零格、第一格。

table[0] = 1; table[1] = 1;

尚待計算的部份就是「爬完兩階」的答案、……、「爬完五階」的答案。通常是使用迴圈，按照計算順序來計算。

計算過程的實作方式，有兩種迥異的風格。一種是「往回取值」，是常見的實作方式。

int table[6]; void dp() { // initial for (int i=0; i<=5; i++) table[i] = 0; table[0] = 1; table[1] = 1; // compute for (int i=2; i<=5; i++) table[i] = table[i-1] + table[i-2]; }

另一種是「往後補值」，是罕見的實作方式。

int table[6]; void dp() { // initial for (int i=0; i<=5; i++) table[i] = 0; table[0] = 1; // table[1] = 1; // 剛好可以被算到 // compute for (int i=0; i<=5; i++) { if (i+1 <= 5) table[i+1] += table[i]; if (i+2 <= 5) table[i+2] += table[i]; } }

計算完畢之後，最後印出答案。

void stairs_climbing() { dp(); cout << "爬完五階的踏法有" << table[5] << "種"; int n; while (cin >> n && (n >= 0 && n <= 5)) { cout << "爬完" << n << "階的踏法" << "有" << table[n] << "種"; } }

UVa 495 900 10334

小結

第一。先找到原問題和其子問題們之間的關係，寫出遞迴公式。如此一來，便可利用遞迴公式，用子子問題的答案，求出子問題的答案；用子問題的答案，求出原問題的答案。

第二。確認可能出現的問題全部共有哪些，這樣才能知道要計算哪些問題，才能知道共會花多少時間、多少記憶體。

第三。有了遞迴公式之後，就必須安排出一套計算的順序。大問題的答案，總是以小問題的答案來求得的，所以，小問題的答案是必須先算的，否則大問題的答案從何而來呢？

一個好的安排方式，不但會使程式碼容易撰寫，還可重複利用記憶體空間。

第四。記得先將最小、最先被計算的問題，心算出答案，儲存入表格，內建於程式碼之中。一道遞迴公式必須擁有初始值，才有辦法計算其他項。

第五。實作DP的程式時，會建立一個表格，在表格存入所有大小問題的答案。安排好每個問題的答案在表格的哪個位置，這樣計算時才能知道該在哪裡取值。

切勿存取超出表格的元素，產生溢位情形，導致答案算錯。計算過程當中，一旦某個問題的答案出錯，就會如骨牌效應般一個影響一個，造成很難除錯。

問題描述

有一個長方形的方格棋盤，從左上角開始，欲走至右下角，每次只能往右走一格或者往下走一格。請問有幾種不同走法？

UVa 10599 825 926

Recurrence

對某個位置的方格來說，只可能是從左走來或者從上走來，將這兩種情形分開，便得到遞迴公式：

count(i, j) =
 { 0                               , if i < 0 or j < 0    [Exterior]
 { 1                               , if i = 0             [Initial]
 { 1                               , if j = 0             [Initial]
 { count(i-1, j) + count(i, j-1)   , if i > 0 and j > 0   [Compute]

count(i, j)：從格子 (0, 0) 走到格子 (i, j) 的走法種類數。

如果能夠懂得遞迴關係，就不必強記遞迴公式。如果能看得懂圖解的話，就不必硬背數學式子。

除了遞迴公式之外，這個問題也有一般公式解，會用到排列組合的技巧：http://mathworld.wolfram.com/StaircaseWalk.html

複雜度

時間複雜度分析：令X和Y分別是棋盤的長和寬。每個問題用O(1)時間（用了兩個更小的問題）就可算得，共有X*Y個問題，所以算出所有問題要用O(XY)時間。

空間複雜度分析：共有X*Y個問題，所以要用O(XY)空間，簡單來說就是開一個二維陣列啦！如果不需要紀錄全部問題的答案，只想算出一個特定問題的答案，那只需要一條一維陣列就可以了，也就是O(min(X, Y))空間。

程式碼

const int X = 10, Y = 10; int count[10][10]; void staircase_walk() { // initial for (int i=0; i<X; i++) count[i][0] = 1; for (int j=0; j<Y; j++) count[0][j] = 1; // compute for (int i=1; i<X; i++) for (int j=1; j<Y; j++) count[i][j] = count[i-1][j] + count[i][j-1]; // 輸出結果 cout << "由(0,0)走到(9,9)有" << count[9][9] << 種走法; // cout << "由(0,0)走到(9,9)有" << count[X-1][Y-1] << 種走法; int x, y; while (cin >> x >> y) cout << "由(0,0)走到(x,y)有" << count[x][y] << 種走法; }

程式碼

為了讓程式碼更清爽，這裡把count[]裡面的數值都往右移動一格，如此就可以簡化設定初始值的過程。

const int X = 10, Y = 10; int count[10 + 1][10 + 1]; void staircase_walk() { // initial memset(count, 0, sizeof(count)); count[0][0] = 1; // 只需要設定一格為1 // compute for (int i=0; i<X; i++) // 可以從零開始了 for (int j=0; j<Y; j++) if (i != 0 && j != 0) count[i][j] = count[i-1][j] + count[i][j-1]; // 輸出結果 cout << "由(0,0)走到(9,9)有" << count[10][10] << 種走法; // cout << "由(0,0)走到(9,9)有" << count[X][Y] << 種走法; }

下面是比較奸詐的做法，連判斷式都省略了。這會讓人看得霧煞煞，不建議這麼作。

const int X = 10, Y = 10; int count[10 + 1][10 + 1]; void staircase_walk() { // initial memset(count, 0, sizeof(count)); count[0][1] = 1; count[1][0] = 1; // compute for (int i=0; i<X; i++) for (int j=0; j<Y; j++) count[i][j] = count[i-1][j] + count[i][j-1]; // 輸出結果 cout << "由(0,0)走到(9,9)有" << count[10][10] << 種走法; // cout << "由(0,0)走到(9,9)有" << count[X][Y] << 種走法; }

節省記憶體空間

如果只打算求出一個問題，那麼中途所有的問題其實都不必紀錄下來，只要紀錄最近算出來的問題，讓計算過程可以順利進行就可以了。

使用兩條陣列，就足夠紀錄最近算出來的問題，並且也能夠避免count[i-1][j]造成邊界溢位。這個實作技巧在中文網路上稱做「滚动数组」，「数组」是陣列的意思，「滚动」也就是兩條陣列輪替使用的意思。

const int X = 10, Y = 10; int count[2][10 + 1]; // 兩條陣列，紀錄最近算出來的問題。 void staircase_walk() { // initial memset(count, 0, sizeof(count)); count[0][0] = 1; // compute for (int i=0; i<X; i++) for (int j=0; j<Y; j++) if (i != 0 && j != 0) // 只是多了 mod 2， // 外觀看起來就像兩條陣列輪替使用。 count[i % 2][j] = count[(i-1) % 2][j] + count[i % 2][j-1]; // 輸出結果 cout << "由(0,0)走到(9,9)有" << count[10 % 2][10 % 2] << 種走法; // cout << "由(0,0)走到(9,9)有" << count[X % 2][Y % 2] << 種走法; }

不過事實上，一條陣列就夠了。也不能再少了。

const int X = 10, Y = 10; int count[10 + 1]; // 一條即可 void staircase_walk() { // initial memset(count, 0, sizeof(count)); count[0] = 1; // compute for (int i=0; i<X; i++) for (int j=0; j<Y; j++) if (i != 0 && j != 0) count[j] += count[j-1]; // 累加即可 // 輸出結果 cout << "由(0,0)走到(9,9)有" << count[10] << 種走法; // cout << "由(0,0)走到(9,9)有" << count[Y] << 種走法; }

往其他方向走的話？

如果某些格子上有障礙物呢？其實也很簡單，如果某格有障礙物，在計算過程中，遇到障礙物就把此格的c(i, j)設為零就可以了。

如果也可以往右下斜角走呢？那麼遞迴公式就再修改一下，多加一項c(i-1, j-1)就行了。

如果可以往上下左右走呢？那麼就可以不斷繞圈子，走法就成了無限多種了。寫成遞迴公式的話，就會產生無窮遞迴，永遠也不會結束。

如果也可以往右上斜角走呢？因為不會產生無窮遞迴，所以這是可以解的！

xD/xD表示法

【待補文字】

範例：Largest Empty Rectangle（離散版本）

詳見「Largest Empty Rectangle」系列文章。

範例：Longest Common Subsequence

詳見「Longest Common Subsequence: Dynamic Programming」。

範例：Longest Palindrome Substring

詳見「Longest Palindrome Substring」。

範例：Maximum Subarray

詳見「Maximum Subarray」。

範例：Bitonic Euclidean TSP（Under Construction!）

D[i][j] 表示一条从点i到点n再到点j的一条最短的双调最短路径的长度。状态转移方程需要画图才可以得到（而且这里还有一部反推的步骤。）因为如果从正面考虑的话… 通过选择不同的路径。D[i][j] 可以推出的状态是 D[i-1][j] 和 D[i-1][i] … 因而最后得到的结果就是这个了。

if (i+1==j) for (k=i+2;k<=n;k++) D[i][j] = min(D[i][j], D[j][k] + dist(i, k));
else D[i][j] = min(D[i][j], D[i+1][j] + dist(i, i+1));

const double INF = 1e6; const int N = 51; struct po {int x, y;} G[N]; double D[N][N]; int n; double dist(int a, int b) { return sqrt((G[a].x-G[b].x)*(G[a].x-G[b].x) + (G[a].y-G[b].y)*(G[a].y-G[b].y)); } void solve() { D[n-1][n] = dist(n-1, n); int i, j, k; for (i=n-2;i>=0;i--) for (j=n;j>i;j--) { D[i][j] = INF; if (i+1==j) for (k=i+2;k<=n;k++) D[i][j] = min(D[i][j], D[j][k] + dist(i, k)); else D[i][j] = min(D[i][j], D[i+1][j] + dist(i, i+1)); } } int main() { while (cin >> n) { for (int i=1;i<=n;i++) cin >> G[i].x >> G[i].y; G[0] = G[1]; solve(); cout << fixed << setprecision(2) << D[0][1] << endl; } }

PKU 2677

範例：0/1 Knapsack Problem

詳見「0/1 Knapsack Problem」。

範例：Word Wrap（Line Breaking）

一大段的英文段落，適當的將文字換行，使排版整齊、不超過紙張邊界。

至於中文字，方方正正，無此問題。

【待補簡例】【待補圖片】

想要節省紙張空間：就把字儘量往前擠，擠不下則換另外一行，是Greedy演算法。

const int width = 10; // 限制寬度 const char s = "This is a book, and that is a pen."; string words[100]; // 儲存各個英文字 int N = 0; // 英文字數 void wordwarp() { /* 將段落拆成字 */ istringstream sin(s); string word; while (sin >> word) words[N++] = word; /* 排版 */ int w = 0; // 目前的寬度 for (int i=0; i<N; ++i) { if (w + 1 + words.size() <= width) { // 不必換行 w += 1 + words[i].size(); cout << ' ' << words[i]; } else { // 需要換行 w = words[i].size(); cout << '\n' << word[i]; } } cout << '\n'; }

想讓行末留白整齊，文字需要均勻散佈於各行，讓視覺觀感變好：就規定行末空白不得太多，設計一評分機制，再用Dynamic Programming求得最佳的留白方式。分割問題的原則是：窮舉段落當中每一個字作為一行的開頭，並窮舉一行該擠入多少字數。

UVa 709 848 400

範例：Longest Increasing Subsequence

把解答編入狀態之中。

詳見「Longest Increasing Subsequence: Dynamic Programming」最後出現的那一篇。

UVa 10157

bitset

bitset是一串二進位數字，每一個位元分別代表一件東西，1代表開啟，0代表關閉。例如現在有十個燈泡，編號設定為零到九，其中第零個、第一個、第四個、第八個燈泡是亮的，剩下來的燈泡是暗的，我們可以用一個10 bit的二進位數字0100001001，來表示這十個燈泡現在的亮暗狀態。

如果想替各種狀態做進一步的記錄，我們可以建立一個大小為2^10的陣列，便囊括了所有可能的狀態。這個陣列的每一格，就代表一種燈泡開關的狀態，可以進行記錄。

int array[1<<10]; array[521] = 想記錄的數字; /* 100001001(2進位) = 521(10進位) */

當狀態數量呈指數成長，可以利用bitset作為狀態。

範例：Maximum Cardinality Matching

大意：給一張圖，相鄰的兩點可匹配在一起，求這張圖的最大匹配方式及匹配數目。

此題有多項式時間的解法，不過很難實作。用DP雖然慢了些，但簡單多了，只要把一對匹配在一起的點拿掉，就可以得到遞迴公式：

c[s] = max ( c[s-{i}-{j}] + adj[i,j] )

c[s+{i}+{j}] = max ( c[s] + adj[i,j] )

i、j：點。
s：點集合。
c[s]：s當中的點，所構成的最大匹配數。
adj[i,j]：adjacency matrix。邊ij暢通就是1，不暢通就是0。

實作時，可利用bitset做為s的資料結構，匹配過的點都標成1，未匹配的點都標成0。

這個方法的時間複雜度為O(2^N * N^2)，空間複雜度為O(2^N)。

這個方法需要大量記憶體，所以無法計算N很大的情況，何況編譯器也不准我們開太大的陣列，N=28就是極限了。這個方法同時也需要大量時間，以現在的個人電腦來說，N=17就已經要花上幾分鐘才能求出答案了。

// top-down DP const int N = 10; // 點的數目 int dp[1<<N]; // lookup table for memoization bool ok[1<<N]; // 記錄lookup table是否已存值 int adj[N][N]; // adjacency matrix。暢通為1，否則為0。 bool MCM(int s) { if (s == 0) return true; if (ok[s]) return dp[s]; for (int i=0; i<N; ++i) for (int j=i+1; j<N; ++j) if (s & ((1<<i) | (1<<j))) { // ss = s - {i} - {j}; int ss = s ^ (1<<i) ^ (1<<j); dp[s] >?= MCM(ss) + adj[i][j]; } ok[s] = true; return dp[s]; } int MCM() { memset(dp, 0, sizeof(dp)); memset(ok, false, sizeof(ok)); return MCM((1<<N)-1); }

這個演算法可以再修正，讓時間複雜度成為O(2^N * N)，各位可以試試看。

UVa 10888 10911 11439 10296 11156

範例：Hamilton Path

大意：從一張圖上找到一條路徑，剛好每一個點都去過一次。有可能找不到。

此題尚無多項式時間的解法。最容易的解法是使用backtracking，窮舉圖上所有點的各種排列方式，一種排列方式當作是一條路徑，並判斷該路徑是不是Hamilton Path。

把一條路徑的最後一條邊拆掉的話，就可以形成遞迴公式。注意到路徑的端點，當端點不同，結果會不同，所以需要另外一個維度來記錄路徑的端點：

path[s,j] = or_all ( path[s-{j},i] && adj[i,j] )

path[s+{j},j] = or_all ( path[s,i] && adj[i,j] )

i、j：點。
s：點集合。
path[s,j]：經過s當中所有點且最後一點是j的路徑，如果暢通就是true，不暢通就是false。
adj[i,j]：adjacency matrix。邊ij暢通就是true，不暢通就是false。

const int N = 10; // 點的數目 bool dp[1<<N][N]; // lookup table for memoization bool ok[1<<N][N]; // 記錄lookup table是否已存值 bool adj[N][N]; // adjacency matrix。暢通為true，否則為false。 bool path(int s, int s_size, int j) { if (s_size == 1) return true; // s只有一個位元是1 if (ok[s][j]) return dp[s][j]; ok[s][j] = true; for (int i=0; i<N; ++i) if (i != j && s & (1<<i)) if (path(s ^ (1<<j), s_size-1, i) && adj[i][j]) return dp[s][j] = true; return dp[s][j] = false; } bool Hamilton_Path() { memset(dp, false, sizeof(dp)); memset(ok, false, sizeof(ok)); for (int i=0; i<N; ++i) if (path((1<<N)-1, N, i)) return true; return false; }

附上一個不正確的遞迴公式：

path[s,n] = or_all ( path[s-{i},n-1] && adj[i,j] )

i、j：點。
s：點集合。
n：已經去過的地點數目。
path[s,n]：經過s當中所有點且經過了n個點的路徑，如果暢通就是true，不暢通就是false。
adj[i,j]：adjacency matrix。邊ij暢通就是true，不暢通就是false。

計算path[N個1組成的二進位數字][N]的時候會產生錯誤。

UVa 216 10068 10496 10818 10937 10944 10605 10890 265

範例：Hamilton Circuit of Grid Graph

http://blog.sina.com.cn/s/blog_51cea4040100gmky.html

UVa 10572 10531 ICPC 4789 4793 Timus 1519

UVa 10952

範例：Subset Sum Problem / Partition Problem

參照Money Changing Problem之湊得某個價位的錢幣用量有哪幾種。

【尚待整理】

UVa 242 10032 10690 10930

deque

deque = double-ended queue，兩端都可push和pop的queue。

遞迴分割出來的問題，把某些問題依大小排列，有時候，問題的答案恰好也會依大小排列。此時把子問題的答案，按照大小順序放入deque，就很容易判斷原問題的答案。

【待補文字】

一、基本型（不遞迴）

f(i) =    min    { d[j] }
      j = i-x ~ i

f(i) =    min　  { d[i - j] }
      j = x ~ 0

d[j]丟入deque即可。視窗極小值。

類似題是TIOJ 1566簡單易懂的城市。

二、外加常數型（不遞迴）

f(i) =    min    { d[j] + c[i] } =    min    { d[j] } + c[i]
      j = i-x ~ i                 j = i-x ~ i

c[i]先拿掉，只用d[j]丟入deque。全部算好之後，最後每個f(i)再加上c[i]。

f(i) =    min    { d[j] + c[j] }
      j = i-x ~ i

其實就是基本型嘛。

三、連續和型（不遞迴）

f(i) =    min    { s[j...i] } =    min    { s[1...i] - s[1...j-1] }
      j = i-x ~ i              j = i-x ~ i

     =    min    { c[j] + d[j] }
      j = i-x ~ i

弄一弄就變成基本型。

類似題是IOI 2008 Island。

一、基本型

d(i) =     min     { d(j) }
      j = i-x ~ i-1

沒有特色的題目。其實就是求初始值的最小值嘛。

PKU 3250

二、外加常數型

d(i) =     min     { d(j) + c[j] }
      j = i-x ~ i-1

放入deque之前就先把c[j]給加好。

d(i) =     min     { d(j) + c[i] } =     min     { d(j) } + c[i]
      j = i-x ~ i-1                 j = i-x ~ i-1

d(j) + c[i]拿掉c[i]之後放入deque，但是要記得放入deque之前要加回c[j]以湊成正確的d(j)。似乎可以改寫成上面的式子。

d(i) =     min     { d(j) + c[j] + c[i] } =     min     { d(j) + c[j] } + c[i]
      j = i-x ~ i-1                        j = i-x ~ i-1

有一點太過火了。總之就是放入deque之前要加上c[j]與c[i]。

三、外加連續和型

d(i) =     min     { d(j) + s[j+1...i] } =     min     { d(j) + c[i] - c[j] }
      j = i-x ~ i-1                       j = i-x ~ i-1

這個玩意最厲害的地方，是在設計遞迴式的時候，可以把每一個狀態i都預先抽一個a[i]值出來，當作s[]。

這一型可以視作四邊形不等式的特例，剛好函數不凹不凸是平的，是平的就等價於是連續和的意思。

類似題是USACO Elite 2010 US Open Gold Cow Hopscotch，好長。

類似題是有限背包問題。

範例：Longest Plateau

在一個排序過的數列中，相同的數字會連續出現。找出連續最多次的次數。一串連續相同的數字稱作一個plateau，而這個問題也就是要找出最長的plateau。

這個問題跟Longest Empty Interval有點像，不過這個問題卻有一個精妙的解法，不需要用到Dynamic Programming。這讓我們多了一種思考問題的方式。

int a[10] = {1,1,2,2,2,2,3,3,5,6}; int longest_plateau() { int length = 1; // 長度至少為1 for (int i=1; i<10; ++i) if (x[i] == x[i-length]) length++; return length; }

範例：【尚未有正式名稱】

ICPC 4726

範例：1-Center Problem

詳見「1-Center Problem」。

範例：Bounded Knapsack Problem

詳見「Bounded Knapsack Problem」。

求最大值、最小值問題當中，有些問題具有非常強的特性，可以快速的找到正確的子問題。

當recurrence具有特殊的遞增或遞減性質時，便可有辦法加速。【待補凸四邊形不等式】

http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=fcaa846ddcba22c1c63777723152ba9492a9f2218

【待補文字】

範例：Matrix Chain Multiplication

矩陣乘法具有結合率。在一連串的矩陣乘法中，可以從中任取兩個相鄰的矩陣相乘，先行結合成一個新矩陣，也不會改變所有矩陣相乘之後的結果。

在一連串的矩陣乘法中，無論從何處開始相乘其結果都不變，然而計算速度卻有差異。兩個矩陣大小為a x b及b x c，其相乘需要O(a*b*c)的時間（當然還可以更快，但此處不討論），那麼一連串的矩陣乘法，需要多少時間呢？

這個問題在許多地方都找得到資料，故只略述。從最後一次相乘的角度來看，原來的一連串矩陣，可從最後一次相乘的地方分開，便能將原問題化作兩串矩陣相乘，然後再合併起來。分割問題的方法類似於「Fast Exponentiation」，但在本問題中，並非固定地對半分，而是同時考慮所有可能的分法。

當然也可以印出矩陣相乘的順序。只要另外再用一個陣列來紀錄每次相乘的位置就行了。

f(i, j) = min { f(i, k) + f(k+1, j) + r[k] * c[k] * r[k+1] }
         i≤k< j

f(i, j)：從第i個矩陣乘到第j個矩陣，最少的相乘次數。
r[i]：第i個矩陣的row數目。
c[i]：第i個矩陣的column數目。

f(i, j) = min( f(i,   i) + f(i+1, j) + r[i]   * c[i]   * r[i+1] ,
               f(i+1, i) + f(i+2, j) + r[i+1] * c[i+1] * r[i+2] ,
               ...                                              ,
               f(j-1, j) + f(j,   j) + r[j-1] * c[j-1] * r[j]   );

現今已能在O(NlogN)時間內解決Matrix Chain Multiplication：http://historical.ncstrl.org/litesite-data/stan/CS-TR-81-875.pdf。

UVa 348 442

範例：Optimal Triangulation

【待補文字】

範例：Optimal Binary Search Tree

問題說明：略！總之就是所有鍵值的「深度」乘上「權重（出現頻率）」的總和要最小。

和Matrix Chain Multiplication相同，窮舉所有可以當作root的鍵值，並以root將原來的樹分作左右兩棵子樹，便縮小了問題。

所有的子問題共有O(N^2)個，每個子問題需要窮舉O(N)種分割點，故時間複雜度為O(N^3)。

下面是計算Optimal Binary Search Tree權重的程式碼，至於印出一棵Optimal Binary Search Tree的程式碼就不提供了。

// 將陣列邊界左右各加一格，如此可省去一些判斷陣列邊界的麻煩。 // 鍵值排序後，各自對應的出現頻率。最左邊和最右邊是額外加上的空格子。 int freq[5+2] = {0, 4, 6, 12, 2, 5, 0}; int sum[5+2][5+2]; // 連續區間和 int c[5+2][5+2]; // 實行DP所用的陣列。初始化為零。 int path[5+2][5+2]; // 用來紀錄左右子樹的分割點 void OptimalBinarySearchTree() { /* 先計算連續區間和。之後就會輕鬆多了。 */ for (int i=0; i<5; ++i) // 區間的寬度 for (int j=1; j+i<=5; ++j) // 區間的起點 sum[j][j+i] = freq[j] + sum[j+1][j+i]; /* 計算最佳的二元搜尋樹。 */ for (int i=0; i<5; ++i) // 區間的寬度 for (int j=1; j+i<=5; ++j) // 區間的起點 { int c[j][j+i] = 1e9; for (int k=j; k<=j+i; ++k) // 分割點 if (c[j][k-1] + c[k+1][j+i] + sum[j][j+i] < c[j][j+i]) { c[j][j+i] = c[j][k-1] + c[k+1][j+i] + sum[j][j+i]; path[j][j+i] = k; } } cout << "最佳的二元搜尋樹的平均搜尋成本為" << c[1][5]; }

由於第二層迴圈實行時，sum[j][j+i]都維持定值，也不影響最大值的判斷，故可將之移到迴圈外面去。加法次數減少，會稍微快一點。

for (int j=1; j+i<=5; ++j) { int c[j][j+i] = 1e9; for (int k=j; k<=j+i; ++k) if (c[j][k-1] + c[k+1][j+i] < c[j][j+i]) { c[j][j+i] = c[j][k-1] + c[k+1][j+i]; // 移走 path[j][j+i] = k; } c[j][j+i] += sum[j][j+i]; // 移到這裡來 }

迴圈判斷式中，關於區間起點的範圍，與其用減法計算區點起點的界限，不如簡單想成區間終點不超過陣列邊界。

for (int i=0; i<5; ++i) // 區間的寬度 for (int j=1; j<=5-i; ++j) // 用減法計算區間起點的界限 // 不確定j+i會不會超過邊界 sum[j][j+i] = freq[j] + sum[j+1][j+i]; for (int i=0; i<5; ++i) for (int j=1; j+i<=5; ++j) // 區間終點不超過陣列邊界 // 對應到此處的index，可確定j+i不會超過陣列邊界。 sum[j][j+i] = freq[j] + sum[j+1][j+i];

細心的觀察者們，可以發現每次計算一個子問題時，總是要窮舉所有的分割點。然而有些分割點很明顯地是錯誤的，尤其是靠近區間邊界的那些分割點，實在不太可能將兩顆子樹分的夠均勻、令總和最小。

另外這個問題還有一個特性。相近的子問題，其分割點的位置也很相近。例如子問題[a,b]的分割點，應該會與子問題[a-1,b]、[a+1,b]的分割點差不多，因為分割出來的左右子樹頂多也只差了一個鍵值，考量到左右子樹要均勻才行，可推論總成本、子樹的形狀、分割點的位置應該都是差不多的。

子問題[a,b]的分割點，必定位於更小的子問題[a+1,b]和[a,b-1]的分割點之間。如此一來，每次計算一個子問題時，就不必窮舉所有的分割點，只要找更小的子問題[a+1,b]和[a,b-1]的分割點之間的分割點即可，為常數個（請各位自行觀察一下）。

由於檢查分割點的次數變成常數次，所以時間複雜度為O(1)。計算O(N^2)個子問題時，時間複雜度就是O(N^2)了。

for (int k=path[j+1][j+i]; k<=path[j][j+i-1]; ++k) // 分割點

UVa 10304

Optimal Binary Search Tree的相似產物

這裡整理了三種很相像的樹，都是令所有鍵值的「深度」乘上「權重（出現頻率）」的總和最小。

Optimal Binary Search Tree：樹上所有點都是鍵值，且鍵值須照大小順序安排。可用Dynamic Programming解決，時間複雜度為O(N^3)，可加速至O(N^2)。

Optimal Alphabetic Binary Tree：只有葉子是鍵值，且鍵值前後順序需固定。可用Greedy解決，時間複雜度為O(NlogN)。

Optimal Binary Code Tree（Huffman Tree）：只有葉子是鍵值，且鍵值順序隨意。可用Greedy解決，時間複雜度為O(NlogN)。

Companion Matrix

把一個數列的遞迴式，化作「友矩陣」之後，計算數列的第N項時，變成矩陣次方計算。

1.
recurrence:
f(n) = p * f(n-1) + q * f(n-2) + r * f(n-3)
f(2) = 2
f(1) = 1
f(0) = 0

another style:
f(0) = 0
f(1) = 1
f(2) = 2
a * f(n) + b * f(n+1) + c * f(n+2) = f(n+3)

2.
     [ f(0) ]   [ 0 ]        [ f(n)   ]       [ 0 1 0 ]
F0 = [ f(1) ] = [ 1 ]   Fn = [ f(n+1) ]   A = [ 0 0 1 ]
     [ f(2) ]   [ 2 ] ,      [ f(n+2) ] ,     [ a b c ]

         [ 0 1 0 ]   [ f(0) ]   [   0    + 1*f(1) +   0    ]   [ f(1) ]
A * F0 = [ 0 0 1 ] * [ f(1) ] = [   0    +   0    + 1*f(2) ] = [ f(2) ] = F1
         [ a b c ]   [ f(2) ]   [ a*f(0) + b*f(1) + c*f(2) ]   [ f(3) ]

重點在於最後一橫列。其他只是簡單位移。
A就是友矩陣。

3.
F1 = A * F0   = A^1 * F0
F2 = A * F1   = A^2 * F0
 ⋮     ⋮            ⋮
Fn = A * Fn-1 = A^(n-1) * F0

4.
         [ f(f-2) ]
Fn-3+1 = [ f(f-1) ] = A^(n-3) * F0
         [ f(n)   ]
           ^^^^ here is f(n)!

矩陣的N次方，只要用O(logN)次矩陣乘法就能求得，原理是Divide and Conquer，可參考「Fast Exponentiation」。也就是說，數列的第N項，總共只要用O(log(N-M))次矩陣乘法就能求得。M是遞迴式的次元數，也是友矩陣的長與寬。

當數列的遞迴式為M次元，要計算數列的第N項時，有兩種計算方式：一、Dynamic Programming：可以順便算出第一項到第N項，由小到大一項一項計算，並存在表格中，需時O(N + (N-M) * M) = O((N-M) * M)；二、Companion Matrix暨Divide and Conquer：只能算出第N項，需時O(log(N-M) * M^3 + M^2) = O(log(N-M) * M^3)，當然了，矩陣相乘還可以更快。

當M是常數時，時間複雜度會更美麗，DP為O(N)，D&C為O(logN)。

void Fibonacci_sequence(int n) { if (n < 0) return; // 建立F0向量 // f(0) = f(1) = 1 Matrix F0(2, 1); F0[0][0] = 0, F0[0][1] = 1; if (n < 2) { cout << F[0][n]; // F0向量已經有第N項 return; } // 建立Companion Matrix // 1 * f(n) + 1 * f(n+1) = f(n+2) Matrix A(2, 2); A[0][0] = 0, A[0][1] = 1, A[1][0] = 1, A[1][1] = 1; // 計算Fn向量 Matrix Fn(2, 1); Fn = (A ^ (n-1)) * F0; // 欲求出第N項的值 cout << Fn[0][0]; // 印出第N項的值 // 只算到Fn-m+1其實就行了，m等於2。 Matrix Fx(2, 1); Fx = (A ^ (n-2)) * F0; // 欲求出第N項的值 cout << Fx[0][1]; // 印出第N項的值 }

此手法的精髓，是將資料以不同型態呈現。轉換數域後，利用新數域的特性，讓計算方式變得更簡潔，快速求得答案。影像處理的Hough transform也是一個好例子。

當遇到一個難纏的問題，不妨換換思考角度，以不同面向來看待資料，或許能找到不錯的新方法。

UVa 10518 10655 10743 10754 10870