前言
最近幫同學寫一個程序，給出100多個金額，用數組表示為money[1-100]，再給出一個數額SUM。如果money數組裡面有哪幾項之和等於SUM，那麼這幾項就是符合條件的一個組合。現在需要做的是，找出所有符合要求的組合。
舉一個簡單的例子，假設money為{1,1,2,3,4}，和為6的所有組合為1+1+4, 1+2+3，1+2+3，2+4。
對於我同學給的這個程序要求，不算不知道，一算嚇一跳，100個數的所有組合情況是2的100次方，是天文數字了。（本機測試2的32次方次數的浮點運算消耗30秒左右時間）
所以沒有辦法羅列出所有的組合，而且在維基百科上查找NPC問題(Non-deterministic Polynomial complete problem非確定多項式完備問題）時，第一個例子就是這種子集合加總問題（說白一點就是組合之和）。維基百科上提到：“這個問題的答案非常容易驗證，但目前沒有任何一個夠快的方法可以在合理的時間內（意即多項式時間）找到答案。只能一個個將它的子集取出來一一測試，它的時間復雜度是Ο（2n），n是此集合的元素數量。”
當然，不能因為羅列所有的組合是不可行的，就不寫這個程序了吧，代碼是死的，人是活的。可以制定策略嘛，比如說如果一個組合裡面最多只能有5項；嘗試遍歷組合的時候，只要找到了10種或者20種組合，後面的就不再計算了。而對於實在搜索不到的組合，我們可以采用超時的方式，比如計算30秒或1分鐘之後就不再計算了，而是返回沒有找到可行的組合。
說了這麼多，好像和我寫的標題還沒有什麼聯系，其實是這樣的，一開始我是采用回溯法去解決上面的問題的，但是我一直在想是不是可以用背包算法或者動態規劃的算法來寫這個程序（當然最後得到的結論是不可行）。
因為以前看過動態規劃方面的一些資料，現在又忘的差不多了，所以想回頭看一下，順便學習一下。= =
這裡有一篇很不錯的講動態規劃的文章：http://hawstein.com/posts/dp-novice-to-advanced.html，裡面通過實例由淺入深的講解了動態規劃的使用。下面我舉一下裡面的兩個例子。
第一個例子 需要的最少硬幣數：
如果我們有面值為1元、4元和5元的硬幣若干枚，如何用最少的硬幣湊夠12元（12可替換為任意的N>0）？
注意：在這裡貪心算法獲得的結果不是最優的，如果按照每次都優先選最大面值的，那麼會先拿兩次5元得到10元，剩下的兩元再拿兩個1元的，總共需要4枚硬幣。而更優化的方案是拿3枚4元的硬幣。
下面我們就來看看該如何解決這個問題。
根據已經有的硬幣面值，我們知道最後一次可以選擇的硬幣有3種方案（1元，4元和5元），如果最後一次是選擇1元硬幣湊夠12元的，那麼倒數第二步就應該是湊夠了12-1= 11元。同理，如果最後一次是選擇4元湊夠12元的，則倒數第二步就應該是湊夠了12-4 = 8元，如果最後一次是選擇5元而湊夠12元的，則倒數第二步就應該是湊夠了12-5 = 7元。
換句話說：只有3種狀態能夠通過只取一枚硬幣就湊夠12元，分別是11元、8元、7元。現在假設湊夠11元、8元、7元所需要的最少硬幣數量是x、y、z，那麼湊夠12元所需要的最少硬幣數量就是x,y,z裡面的最小值 + 1。用表達式表示就是min(x,y,z)+1，從遞歸的角度來看問題就被遞歸下降分解了，從原來的求湊夠12元需要的最少硬幣數轉換成了求湊夠11元、8元、7元所需要的最少硬幣數。那麼把這種遞歸下降分解的思路繼續拓展下去，最終會終止到1元硬幣的情況。
我們用N(i)表示湊夠i元需要的最少硬幣數量。那麼N(12) = min ( N(11), N(8), N(7) ) + 1. 轉換成更一般的公式就是N(i) = min ( N(i-1), N(i-4), N(i-5) ) + 1.根據這個公式我們可以寫出遞歸函數，代碼如下：
[cpp]
int GetMinCoinCount(int nSum)
{
if (1 == nSum || 4 == nSum || 5 == nSum)
{
return 1;
}
if (nSum > 5)
{
return MIN_THREE(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4), GetMinCoinCount(nSum-5))+1;
}
else if (nSum > 4)
{
return MIN_TWO(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4))+1;
}
else
{
return GetMinCoinCount(nSum-1)+1;
}
}
int GetMinCoinCount(int nSum)
{
if (1 == nSum || 4 == nSum || 5 == nSum)
{
return 1;
}
if (nSum > 5)
{
return MIN_THREE(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4), GetMinCoinCount(nSum-5))+1;
}
else if (nSum > 4)
{
return MIN_TWO(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4))+1;
}
else
{
return GetMinCoinCount(nSum-1)+1;
}
}遞歸雖然代碼寫起來很簡單，理解起來也不困難，但是效率非常低，究其原因就是因為我們重復計算了太多中間值，比如用上面的代碼計算湊夠12元所需要的最少硬幣數，上面的這個函數被調用了2620次之多（在函數內部加一個靜態變量或全局變量，進行遞增計算即可）。
當需要湊夠27元時，GetMinCoinCount函數被調用次數已經達到29,1208,9123次（29億）。消耗的時間在幾十秒的數量級。下面是測試代碼和測試結果。
[cpp]
for (int m = 12; m < 30; m++)
{
g_i = 0;
int n = GetMinCoinCount(m);
printf("計算湊成%d元最少需要的硬幣數量,調用GetMinCoinCount函數0x%08X次。\r\n", m, g_i);
}
計算湊成12元最少需要的硬幣數量,調用GetMinCoinCount函數0x00000A3C次。
計算湊成13元最少需要的硬幣數量,調用GetMinCoinCount函數0x0000184B次。
計算湊成14元最少需要的硬幣數量,調用GetMinCoinCount函數0x00003535次。
計算湊成15元最少需要的硬幣數量,調用GetMinCoinCount函數0x00003F7A次。
計算湊成16元最少需要的硬幣數量,調用GetMinCoinCount函數0x00011692次。
計算湊成17元最少需要的硬幣數量,調用GetMinCoinCount函數0x0004951B次。
計算湊成18元最少需要的硬幣數量,調用GetMinCoinCount函數0x000A1756次。
計算湊成19元最少需要的硬幣數量,調用GetMinCoinCount函數0x001561CA次。
計算湊成20元最少需要的硬幣數量,調用GetMinCoinCount函數0x00180DE3次。
計算湊成21元最少需要的硬幣數量,調用GetMinCoinCount函數0x006A7855次。
計算湊成22元最少需要的硬幣數量,調用GetMinCoinCount函數0x01C2A51C次。
計算湊成23元最少需要的硬幣數量,調用GetMinCoinCount函數0x03E4E8B7次。
計算湊成24元最少需要的硬幣數量,調用GetMinCoinCount函數0x083F6AC5次。
計算湊成25元最少需要的硬幣數量,調用GetMinCoinCount函數0x09447736次。
計算湊成26元最少需要的硬幣數量,調用GetMinCoinCount函數0x29019F66次。
計算湊成27元最少需要的硬幣數量,調用GetMinCoinCount函數0xAD92F423次。
for (int m = 12; m < 30; m++)
{
g_i = 0;
int n = GetMinCoinCount(m);
printf("計算湊成%d元最少需要的硬幣數量,調用GetMinCoinCount函數0x%08X次。\r\n", m, g_i);
}
計算湊成12元最少需要的硬幣數量,調用GetMinCoinCount函數0x00000A3C次。
計算湊成13元最少需要的硬幣數量,調用GetMinCoinCount函數0x0000184B次。
計算湊成14元最少需要的硬幣數量,調用GetMinCoinCount函數0x00003535次。
計算湊成15元最少需要的硬幣數量,調用GetMinCoinCount函數0x00003F7A次。
計算湊成16元最少需要的硬幣數量,調用GetMinCoinCount函數0x00011692次。
計算湊成17元最少需要的硬幣數量,調用GetMinCoinCount函數0x0004951B次。
計算湊成18元最少需要的硬幣數量,調用GetMinCoinCount函數0x000A1756次。
計算湊成19元最少需要的硬幣數量,調用GetMinCoinCount函數0x001561CA次。
計算湊成20元最少需要的硬幣數量,調用GetMinCoinCount函數0x00180DE3次。
計算湊成21元最少需要的硬幣數量,調用GetMinCoinCount函數0x006A7855次。
計算湊成22元最少需要的硬幣數量,調用GetMinCoinCount函數0x01C2A51C次。
計算湊成23元最少需要的硬幣數量,調用GetMinCoinCount函數0x03E4E8B7次。
計算湊成24元最少需要的硬幣數量,調用GetMinCoinCount函數0x083F6AC5次。
計算湊成25元最少需要的硬幣數量,調用GetMinCoinCount函數0x09447736次。
計算湊成26元最少需要的硬幣數量,調用GetMinCoinCount函數0x29019F66次。
計算湊成27元最少需要的硬幣數量,調用GetMinCoinCount函數0xAD92F423次。
顯然，這樣的遞歸算法是不可取的。我們分析一下問題的原因，就是因為同一個數值在遞歸函數中進行了多次計算，比如我們仍然以湊夠12元為例，下圖可以形象地展示計算過程：
由此圖我們可以看出，存在大量的重復計算。比如圖中的7。整個樹上的節點增長速度是指數級的，樹的最大深度為12層。每個節點的孩子節點為0到3個不等。
如果我們能夠消除重復計算，將大大提升計算的速度。我們可以將計算出來的中間值保存起來，等下一次需要時直接拿來用，而不是又重新去計算一遍。
那麼中間狀態有多少種情況呢？對於湊成12元來說，所有可能需要用到的中間狀態也就是從1元到11元。所以我們用一個數組來表示，代碼修改如下。
[cpp]
int g_nMinArray[100] = {};
int g_i = 0;
int GetMinCoinCount2(int nSum)
{
g_i++;
if (0 != g_nMinArray[nSum])
{
return g_nMinArray[nSum];
}
if (1 == nSum || 4 == nSum || 5 == nSum)
{
g_nMinArray[nSum] = 1;
return 1;
}
if (nSum > 5)
{
g_nMinArray[nSum] = MIN_THREE(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4), GetMinCoinCount2(nSum-5))+1;
}
else if (nSum > 4)
{
g_nMinArray[nSum] = MIN_TWO(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4))+1;
}
else
{
g_nMinArray[nSum] = GetMinCoinCount2(nSum-1)+1;
}
return g_nMinArray[nSum];
}
int g_nMinArray[100] = {};
int g_i = 0;
int GetMinCoinCount2(int nSum)
{
g_i++;
if (0 != g_nMinArray[nSum])
{
return g_nMinArray[nSum];
}
if (1 == nSum || 4 == nSum || 5 == nSum)
{
g_nMinArray[nSum] = 1;
return 1;
}
if (nSum > 5)
{
g_nMinArray[nSum] = MIN_THREE(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4), GetMinCoinCount2(nSum-5))+1;
}
else if (nSum > 4)
{
g_nMinArray[nSum] = MIN_TWO(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4))+1;
}
else
{
g_nMinArray[nSum] = GetMinCoinCount2(nSum-1)+1;
}
return g_nMinArray[nSum];
}相應的測試代碼如下：
[cpp]
for (int m = 12; m <= 100; m++)
{
g_i = 0;
memset(g_nMinArray, 0, sizeof(g_nMinArray));
int n = GetMinCoinCount2(m);
printf("計算湊成%d元最少需要的硬幣數量,調用GetMinCoinCount2函數%d次。\r\n", m, g_i);
printf("%d\r\n", n);
}
for (int m = 12; m <= 100; m++)
{
g_i = 0;
memset(g_nMinArray, 0, sizeof(g_nMinArray));
int n = GetMinCoinCount2(m);
printf("計算湊成%d元最少需要的硬幣數量,調用GetMinCoinCount2函數%d次。\r\n", m, g_i);
printf("%d\r\n", n);
}
打印輸出的部分結果：
[cpp]
計算湊成94元最少需要的硬幣數量,調用GetMinCoinCount2函數626次。
19
計算湊成95元最少需要的硬幣數量,調用GetMinCoinCount2函數633次。
19
計算湊成96元最少需要的硬幣數量,調用GetMinCoinCount2函數640次。
20
計算湊成97元最少需要的硬幣數量,調用GetMinCoinCount2函數647次。
20
計算湊成98元最少需要的硬幣數量,調用GetMinCoinCount2函數654次。
20
計算湊成99元最少需要的硬幣數量,調用GetMinCoinCount2函數661次。
20
計算湊成100元最少需要的硬幣數量,調用GetMinCoinCount2函數668次。
20
計算湊成94元最少需要的硬幣數量,調用GetMinCoinCount2函數626次。
19
計算湊成95元最少需要的硬幣數量,調用GetMinCoinCount2函數633次。
19
計算湊成96元最少需要的硬幣數量,調用GetMinCoinCount2函數640次。
20
計算湊成97元最少需要的硬幣數量,調用GetMinCoinCount2函數647次。
20
計算湊成98元最少需要的硬幣數量,調用GetMinCoinCount2函數654次。
20
計算湊成99元最少需要的硬幣數量,調用GetMinCoinCount2函數661次。
20
計算湊成100元最少需要的硬幣數量,調用GetMinCoinCount2函數668次。
20
可以看出，通過保存中間狀態的方式，我們將指數級的計算時間縮短到了線性級。
另外，我們上面的思路一直是遞歸的思路，通過將遞歸改成遞推，我們可以減少不必要的函數調用和棧空間開銷，進一步提高計算速度。相應代碼如下：
[cpp]
int GetMinCoin(int nSum)
{
for (int i = 1; i <= nSum; i++)
{
if (1 == i || 4 == i || 5 == i)
{
g_nMinArray[i] = 1;
}
else if (i > 5)
{
g_nMinArray[i] = MIN_THREE(g_nMinArray[i-1], g_nMinArray[i-4], g_nMinArray[i-5])+1;
}
else if (i > 4)
{
g_nMinArray[i] = MIN_TWO(g_nMinArray[i-1], g_nMinArray[i-4])+1;
}
else
{
g_nMinArray[i] = g_nMinArray[i-1]+1;
}
}
return g_nMinArray[nSum];
}
int GetMinCoin(int nSum)
{
for (int i = 1; i <= nSum; i++)
{
if (1 == i || 4 == i || 5 == i)
{
g_nMinArray[i] = 1;
}
else if (i > 5)
{
g_nMinArray[i] = MIN_THREE(g_nMinArray[i-1], g_nMinArray[i-4], g_nMinArray[i-5])+1;
}
else if (i > 4)
{
g_nMinArray[i] = MIN_TWO(g_nMinArray[i-1], g_nMinArray[i-4])+1;
}
else
{
g_nMinArray[i] = g_nMinArray[i-1]+1;
}
}
return g_nMinArray[nSum];
}可以用這段代碼的運行結果和上面遞歸代碼的計算結果進行比較驗證。這個例子就先講到這裡了，其實和斐波那契數列的求法在思想上挺類似（維基百科中文版的動態規劃詞條下就是用斐波那契數列來做例子的）。
在這裡有一個很重要的思想就是保存中間子過程供多次使用，用空間換時間加快算法計算時間，這是動態規劃算法的精髓。
第二個例子 路徑經過的最大值（最小值）：
原題：平面上有N*M個格子，每個格子中放著一定數量的蘋果。從左上角的格子開始， 每一步只能向下走或是向右走，每次走到一個格子就把格子裡的蘋果收集起來， 這樣一直走到右下角，問最多能收集到多少個蘋果。
不妨用一個表格來表示：
{5, 8, 5, 7, 1, 8},
{1, 3, 2, 8, 7, 9},
{7, 8, 6, 6, 8, 7},
{9, 9, 8, 1, 6, 3},
{2, 4,10, 2, 6, 2},
{5, 5, 2, 1, 8, 8},
在這個6X6的表格裡面填寫了一些數表示所在格子中的蘋果數量。根據題目的規則"每一步只能向下走或是向右走"，如果用i表示縱向，用j表示橫向，那麼能夠到達a[i][j]處的只有兩個位置a[i-1][j](上一格)和a[i][j-1]（左邊一格），所以必然是取這兩個位置中比較大的那一個點。依此回溯到a[0][0]，或者從a[0][0]遞推到a[i][j]。
......... , ......... , a[i-1][j]
......... , a[[i][j-1], a[i][j] ,
基於這一點，我們可以從左上角開始將到達第一行和第一列中各點所能收集到的最大蘋果數量填成一張表格。如下：
接下來填第2行，首先是第2行第2列的值，應該填寫為 MAX（A[1][2], A[2][1]）+ A[2][2]對應的蘋果數量。也就是說到達第2行第2列能獲得的最大蘋果數，要看第2行第1列所獲得的蘋果數（6）和第1行第2列所獲得的蘋果數（13），這兩者哪個更大，誰大就取誰的值，顯然第1行第2列所獲得的蘋果數（13）更大，所以用13加上第2行第2列的蘋果數3 = 16，就是到達第2行第2列能獲得的最大蘋果數。同理，填所在格能獲得的最大蘋果數就是看它左面一格和上面一格哪個值更大，就取哪個值再加上自己格子裡面的蘋果數，就是到達此格能獲得的最大蘋果數。依此填完所有格子，最後得到下圖：
所以：到達右下角能夠獲得的最大蘋果數量是76。所經過的路徑可以通過倒推的方法得到，從右下角開始看所在格子的左邊一格和上面一格哪邊大就往哪邊走，如果遇到一樣大的，任選一條即可。
這樣我們可以畫出路線圖，如下圖右邊表格：
這個例子的分析和解決方法大概就是這樣了。在前面第一個例子裡面我們提到：空間換時間是動態規劃的精髓。但是一個問題是否能夠用動態規劃算法來解決，需要看這個問題是否能被分解為更小的問題（子問題）。而子問題之間是否有包含的關系，是區別動態規劃算法和分治法的所在。一般來說，分治法的各個子問題之間是相互獨立的，比如折半查找（二分查找）、歸並排序等。而動態規劃算法的子問題在往下細分為更小的子問題時往往會遇到重復的子問題，我們只處理同一個子問題一次，將子問題的結果保存下來，這就是動態規劃的最大特點。
動態規劃算法總結起來就是兩點：
1 尋找遞推（遞歸）關系，比較專業的說法叫做狀態轉移方程。
2 保存中間狀態，空間換時間。
