一個大問題本身是由許多小問題所組成，且求解小問題的概念，也就是求解大問題的概念，像這種大問題就可以使用動態規劃來求解，而事實上，我倒覺得
動態規劃求解觀念就是遞迴觀念。
假設有一發電廠欲規劃三年內符合總需求機組數的每年購買機組數以使購買總成本最低，如下圖：
我們可以依序購買 3,1,3 ，其成本為6+1+10=17，也可以任序購買 3,2,2 ，其成本為3+4+5=12，如此我們可知 3,2,2 的購買方式比較好。而最佳解該如何求得?以最簡單想法來看，就是把每年的選擇窮舉出來即可，以上題計，只要找出 4^3 種方式，比較那些方式符合總需求機組數且成本最低即可。
但窮舉法總有一天跑不完，如果你的問題是有二十種選擇，且要規劃二十年的話，電腦就沒這能耐跑出來了。
所以此題的作法是把大問題切成小問題，我們不用管三年後該怎麼買，而是永遠只考慮下一年要怎麼買。
從第一年開始，因為至少購買一組，所以我們留下三種購買方式 {1, 2, 3} ，到第二年時，我們把第一年的 1 組，去加上第二年的可購買組數 [0, 1, 2, 3] ，可得到 {1, 2, 3, 4} ;把第一年的 2 組，去加上 [0, 1, 2, 3] 可得到 {2, 3, 4, 5};
依此觀念可得
{1, 2, 3, 4}
{2, 3, 4, 5}
{3, 4, 5, 6}
等方式，這也就是下一年(也就是第二年)的可能購買方式組合。接下來，我們把下一年(也就是第二年)的總數量為 X 的組合找出來，然後留下成本最低的那一種，結果我們可知下一年(也就是第二年)會留下 3, 4, 5, 6 等四種總數量的購買方式：
在第二年的總購買量為 3 時: 1, 2(成本為2+4); 2, 1(成本為3+1); 3, 0(成本為6+0) => 應選 2,1 這一組。
在第二年的總購買量為 4 時: 1, 3(2+5); 2, 2(3+4); 3, 1(6+1) => 剛好都一樣，隨便選 1, 3 吧!
在第二年的總購買量為 5 時: 2, 3(3+5); 3, 2(6+4) => 2, 3
在第二年的總購買量為 6 時: 3, 3(6+5) => 3, 3
所以我們得到在第二年總購買量可為 {3, 4, 5, 6} 而它們的購買方式為 (2, 1), (1, 3), (2, 3), (3, 3) 等四種。
再接下一年，我們把 {3, 4, 5, 6} 再分別與第三年的 [0, 1, 2, 3] 來作組合得到：
在第三年的總購買量為 7 時： (1, 3), 3(成本為7+10); (2, 3), 2(成本為8+5); (3, 3), 1(成本為11+2) => 所以選擇 2, 3, 2，其總成本為 13 。
在第三年的總購買量為 8 時： (2, 3), 3(8+10); (3, 3), 2(11+5) => 3, 3, 2(16)
在第三年的總購買量為 9 時： (3, 3), 3(11+10) => 3, 3, 3(21)
由此，我們選擇 2, 3, 2 為我們的三年購買方式，其總成本為最低，只有 13 。
以上是例題的簡單說明。
我們會把發電廠的
完整問題，以
Python 程式解出。程式說明如下：
解答的資料結構:
Res = {
27: {
'cost': 40 , 'list': [5, 1, 3, 10, 2, 0, 0, 6, 0, 0],
'costlist': [10, 1, 4, 15, 2, 0, 0, 8, 0, 0]
},
....
}
27 代表當年度的總機組數量， cost 值代表在每年購買量為 [5, 1, 3, 10, 2, 0, 0, 6, 0, 0] 時的總成本，
costlist 陣列則是每年購買成本。
成本矩陣：
Cost = [
[0 , 2 , 5 , 7 , 9 , 10 , 12 , 16 , 18 , 19 , 20], # 第一年在各種購買量下的成本。
[0 , 1 , 5 , 7 , 9 , 12 , 15 , 18 , 21 , 25 , 27], # 第二年在各種購買量下的成本。
[0 , 2 , 3 , 4 , 7 , 9 , 10 , 13 , 15 , 19 , 22],
[0 , 1 , 2 , 6 , 7 , 8 , 10 , 11 , 12 , 14 , 15],
[0 , 1 , 2 , 4 , 5 , 7 , 11 , 12 , 14 , 16 , 18],
[0 , 2 , 3 , 6 , 9 , 11 , 12 , 13 , 16 , 17 , 21],
[0 , 2 , 6 , 7 , 8 , 9 , 11 , 14 , 16 , 20 , 22],
[0 , 2 , 4 , 5 , 6 , 7 , 8 , 12 , 14 , 17 , 19],
[0 , 1 , 3 , 5 , 8 , 9 , 10 , 12 , 13 , 17 , 18],
[0 , 3 , 7 , 10 , 12 , 15 , 18 , 21 , 24 , 25 , 27],
]
需求矩陣：
Limit = [3 , 4 , 9 , 11 , 14 , 18 , 18 , 21 , 24 , 27]
運算流程：
主要概念是把前一年度的購買組合與本年度的購買組作交叉組合配對，
會得到本年度的購買組合，每一購買組合的形式如下：
27: {
'cost': 40 , 'list': [5, 1, 3, 10, 2, 0, 0, 6, 0, 0],
'costlist': [10, 1, 4, 15, 2, 0, 0, 8, 0, 0]
},
27 代表當年度的總機組數量， cost 值代表在每年購買量為
[5, 1, 3, 10, 2, 0, 0, 6, 0, 0] 時的總成本，
costlist 陣列則是每年購買成本。
跑完當年度的購買組合後，就把不滿足需求量機組數的購買組合刪除。
等 10 個年度跑完後，再利用 sort_by_cost
函式作排序，把最便宜的購買組合放到最前面。
延伸閱讀：
sort_by_cost 函式的原理：請參考
http://wiki.python.org/moin/HowTo/Sorting#head-10e70070894a1bdb7580127b5cf764a44a2d6d29
for k_i in [k for k in Res.keys() if k ＜ Limit[i]]: del Res[k_i] 的語法等價於：
toDel_k = []
for k in Res.keys():
if k ＜ Limit[i]: toDel_k.append(k)
for k in toDel_k:
del Res[k]
完整程式下載： http://www.hoamon.info/_d/dynamic_programming.py
