今天在網(wǎng)上看到一個講動態(tài)規(guī)劃的文章枷邪，是以01背包為例的，這文章和書上的講解非常不一樣诺凡，令我眼前一亮东揣，于是轉載一下下～～
附上原文地址：
http://www.cnblogs.com/sdjl/articles/1274312.html
對于動態(tài)規(guī)劃，每個剛接觸的人都需要一段時間來理解腹泌，特別是第一次接觸的時候總是想不通為什么這種方法可行嘶卧，這篇文章就是為了幫助大家理解動態(tài)規(guī)劃，并通過講解基本的01背包問題來引導讀者如何去思考動態(tài)規(guī)劃凉袱。本文力求通俗易懂芥吟，無異性，不讓讀者感到迷惑专甩，引導讀者去思考钟鸵，所以如果你在閱讀中發(fā)現(xiàn)有不通順的地方，讓你產(chǎn)生錯誤理解的地方涤躲，讓你難得讀懂的地方棺耍，請跟貼指出，謝謝篓叶！
----第一節(jié)----初識動態(tài)規(guī)劃--------
經(jīng)典的01背包問題是這樣的：
有一個包和n個物品烈掠，包的容量為m羞秤，每個物品都有各自的體積和價值，問當從這n個物品中選擇多個物品放在包里而物品體積總數(shù)不超過包的容量m時左敌，能夠得到的最大價值是多少瘾蛋？[對于每個物品不可以取多次，最多只能取一次矫限，之所以叫做01背包哺哼，0表示不取，1表示取]
為了用一種生動又更形象的方式來講解此題叼风，我把此題用另一種方式來描述取董，如下：
有一個國家，所有的國民都非常老實憨厚无宿，某天他們在自己的國家發(fā)現(xiàn)了十座金礦茵汰，并且這十座金礦在地圖上排成一條直線，國王知道這個消息后非常高興孽鸡，他希望能夠把這些金子都挖出來造福國民蹂午，首先他把這些金礦按照在地圖上的位置從西至東進行編號，依次為0彬碱、1豆胸、2、3巷疼、4晚胡、5、6嚼沿、7估盘、8、9伏尼，然后他命令他的手下去對每一座金礦進行勘測忿檩，以便知道挖取每一座金礦需要多少人力以及每座金礦能夠挖出多少金子，然后動員國民都來挖金子爆阶。
題目補充1：挖每一座金礦需要的人數(shù)是固定的燥透，多一個人少一個人都不行。國王知道每個金礦各需要多少人手辨图，金礦i需要的人數(shù)為peopleNeeded班套。
題目補充2：每一座金礦所挖出來的金子數(shù)是固定的，當?shù)趇座金礦有peopleNeeded人去挖的話故河，就一定能恰好挖出gold個金子吱韭。否則一個金子都挖不出來。
題目補充3：開采一座金礦的人完成開采工作后，他們不會再次去開采其它金礦理盆，因此一個人最多只能使用一次痘煤。
題目補充4：國王在全國范圍內(nèi)僅招募到了10000名愿意為了國家去挖金子的人，因此這些人可能不夠把所有的金子都挖出來猿规，但是國王希望挖到的金子越多越好衷快。
題目補充5：這個國家的每一個人都很老實（包括國王），不會私吞任何金子姨俩，也不會弄虛作假蘸拔，不會說謊話。
題目補充6：有很多人拿到這個題后的第一反應就是對每一個金礦求出平均每個人能挖出多少金子环葵，然后從高到低進行選擇调窍，這里要強調這種方法是錯的，如果你也是這樣想的张遭，請考慮背包模型邓萨，當有一個背包的容量為10，共有3個物品菊卷，體積分別是3先誉、3、5的烁，價值分別是6、6诈闺、9渴庆，那么你的方法取到的是前兩個物品，總價值是12雅镊，但明顯最大值是后兩個物品組成的15襟雷。
題目補充7：我們只需要知道最多可以挖出多少金子即可，而不用關心哪些金礦挖哪些金礦不挖仁烹。
那么耸弄，國王究竟如何知道在只有10000個人的情況下最多能挖出多少金子呢？國王是如何思考這個問題的呢卓缰？
國王首先來到了第9個金礦的所在地（注意计呈，第9個就是最后一個，因為是從0開始編號的征唬，最西邊的那個金礦是第0個）捌显，他的臣子告訴他，如果要挖取第9個金礦的話就需要1500個人总寒，并且第9個金礦可以挖出8888個金子扶歪。聽到這里國王哈哈大笑起來，因為原先他以為要知道十個金礦在僅有10000個人的情況下最多能挖出多少金子是一件很難思考的問題摄闸，但是善镰，就在剛才聽完他的臣子所說的那句話時妹萨，國王已經(jīng)知道總共最多能挖出多少金子了，國王是如何在不了解其它金礦的情況下知道最多能挖出多少金子的呢炫欺？他的臣子們也不知道這個謎乎完，因此他的臣子們就問他了：“最聰明的國王陛下，我們都沒有告訴您其它金礦的情況竣稽，您是如何知道最終答案的呢囱怕？”
得意的國王笑了笑，然后把他最得意的“左毫别、右手”叫到跟前娃弓，說到：“我并不需要考慮最終要挖哪些金礦才能得到最多的金子，我只需要考慮我面前的這座金礦就可以了岛宦，對于我面前的這座金礦不外乎僅有兩種選擇台丛，要么挖，要么不挖砾肺，對吧挽霉？”
“當然，當然”大臣們回答倒变汪。
國王繼續(xù)說道：“如果我挖取第9座金礦的話那么我現(xiàn)在就能獲得8888個金子侠坎，而我將用去1500個人，那么我還剩下8500個人裙盾。我親愛的左部下实胸，如果你告訴我當我把所有剩下的8500個人和所有剩下的其它金礦都交給你去開采你最多能給我挖出多少金子的話，那么我不就知道了在第9個金礦一定開采的情況下所能得到的最大金幣數(shù)嗎番官？”
國王的左部下聽后回答道：“國王陛下庐完，您的意思是如果我能用8500個人在其它金礦最多開采出x個金幣的話，那您一共就能夠獲得 x + 8888個金子徘熔，對嗎门躯？”
“是啊，是啊……如果第9座金礦一定開采的話……”大臣們點頭說到酷师。
國王笑著繼續(xù)對著他的右部下說到：“親愛的右部下讶凉，也許我并不打算開采這第9座金礦，那么我依然擁有10000個人窒升，如果我把這10000個人和剩下的金礦都給你的話缀遍，你最多能給我挖出多少個金子呢？”
國王的右部下聰明地說道：“尊敬的國王陛下饱须，我明白您的意思了域醇，如果我回答最多能購開采出y個金幣的話，那您就可以在y和x+8888之間選擇一個較大者，而這個較大者就是最終我們能獲得的最大金幣數(shù)譬挚，您看我這樣理解對嗎锅铅？”
國王笑得更燦爛了，問他的左部下：“那么親愛的左部下减宣，我給你8500個人和其余金礦的話你能告訴我最多能挖出多少金子嗎盐须？”
“請您放心，這個問題難不倒我”漆腌。左部下向國王打包票說到贼邓。
國王高興地繼續(xù)問他的右部下：“那右部下你呢，如果我給你10000個人和其余金礦的話你能告訴我最多能挖出多少金子嗎闷尿？”
“當然能了塑径！交給我吧！”右部下同左部下一樣自信地回答道填具。
“那就拜托給你們兩位了统舀，現(xiàn)在我要回到我那舒適的王宮里去享受了，我期待著你們的答復劳景∮颍”國王說完就開始動身回去等消息了，他是多么地相信他的兩個大臣能夠給他一個準確的答復盟广，因為國王其實知道他的兩位大臣要比他聰明得多闷串。
故事發(fā)展到這里，你是否在想國王的這兩個大臣又是如何找到讓國王滿意的答案的呢筋量？他們?yōu)槭裁茨軌蛉绱俗孕拍亓耍渴聦嵣纤麄兊拇_比國王要聰明一些，因為他們從國王的身上學到了一點毛甲，就是這一點讓他們充滿了自信。
國王走后具被，國王的左玻募、右部下來到了第8座金礦，早已在那里等待他們的金礦勘測兵向兩位大臣報道：“聰明的兩位大臣一姿，您們好七咧，第8座金礦需要1000個人才能開采，可以獲得7000個金子”叮叹。
因為國王僅給他的左部下8500個人艾栋，所以國王的左部下叫來了兩個人，對著其中一個人問到：“如果我給你7500個人和除了第8蛉顽、第9的其它所有金礦的話蝗砾，你能告訴我你最多能挖出多少金子嗎？”
然后國王的左部下繼續(xù)問另一個人：“如果我給你8500個人和除了第8、第9的其它所有金礦的話悼粮，你能告訴我你最多能挖出多少金子嗎闲勺？”
國王的左部下在心里想著：“如果他們倆都能回答我的問題的話，那國王交給我的問題不就解決了嗎扣猫？哈哈哈菜循！”
因為國王給了他的右部下10000個人，所以國王的右部下同樣也叫來了兩個人申尤，對著其中一個人問：“如果我給你9000個人和除了第8癌幕、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎昧穿？”
然后國王的右部下繼續(xù)問他叫來的另一個人：“如果我給你10000個人和除了第8勺远、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎粤咪？”
此時谚中，國王的右部下同左部下一樣，他們都在為自己如此聰明而感到滿足寥枝。
當然宪塔，這四個被叫來的人同樣自信地回答沒有問題，因為他們同樣地從這兩個大臣身上學到了相同的一點囊拜，而兩位自認為自己一樣很聰明的大臣得意地笑著回到了他們的府邸某筐，等著別人回答他們提出來的問題，現(xiàn)在你知道了這兩個大臣是如何解決國王交待給他們的問題了嗎冠跷？
那么你認為被大臣叫去的那四個人又是怎么完成大臣交給他們的問題的呢南誊？答案當然是他們找到了另外八個人！
沒用多少功夫蜜托，這個問題已經(jīng)在全國傳開了抄囚，更多人的人找到了更更多的人來解決這個問題，而有些人卻不需要去另外找兩個人幫他橄务，哪些人不需要別人的幫助就可以回答他們的問題呢幔托？
很明顯，當被問到給你z個人和僅有第0座金礦時最多能挖出多少金子時蜂挪，就不需要別人的幫助重挑，因為你知道，如果z大于等于挖取第0座金礦所需要的人數(shù)的話棠涮，那么挖出來的最多金子數(shù)就是第0座金礦能夠挖出來的金子數(shù)谬哀，如果這z個人不夠開采第0座金礦，那么能挖出來的最多金子數(shù)就是0严肪，因為這唯一的金礦不夠人力去開采史煎。讓我們?yōu)檫@些不需要別人的幫助就可以準確地得出答案的人們鼓掌吧谦屑，這就是傳說中的底層勞動人民！
故事講到這里先暫停一下劲室，我們現(xiàn)在重新來分析一下這個故事伦仍，讓我們對動態(tài)規(guī)劃有個理性認識。
子問題：
國王需要根據(jù)兩個大臣的答案以及第9座金礦的信息才能判斷出最多能夠開采出多少金子很洋。為了解決自己面臨的問題充蓝，他需要給別人制造另外兩個問題，這兩個問題就是子問題喉磁。
思考動態(tài)規(guī)劃的第一點----最優(yōu)子結構：
國王相信谓苟，只要他的兩個大臣能夠回答出正確的答案（對于考慮能夠開采出的金子數(shù)，最多的也就是最優(yōu)的同時也就是正確的）协怒，再加上他的聰明的判斷就一定能得到最終的正確答案涝焙。我們把這種子問題最優(yōu)時母問題通過優(yōu)化選擇后一定最優(yōu)的情況叫做“最優(yōu)子結構”。
思考動態(tài)規(guī)劃的第二點----子問題重疊：
實際上國王也好孕暇，大臣也好仑撞，所有人面對的都是同樣的問題，即給你一定數(shù)量的人妖滔，給你一定數(shù)量的金礦隧哮，讓你求出能夠開采出來的最多金子數(shù)。我們把這種母問題與子問題本質上是同一個問題的情況稱為“子問題重疊”座舍。然而問題中出現(xiàn)的不同點往往就是被子問題之間傳遞的參數(shù)沮翔，比如這里的人數(shù)和金礦數(shù)。
思考動態(tài)規(guī)劃的第三點----邊界：
想想如果不存在前面我們提到的那些底層勞動者的話這個問題能解決嗎曲秉？永遠都不可能采蚀！我們把這種子問題在一定時候就不再需要提出子子問題的情況叫做邊界，沒有邊界就會出現(xiàn)死循環(huán)承二。
思考動態(tài)規(guī)劃的第四點----子問題獨立：
要知道榆鼠，當國王的兩個大臣在思考他們自己的問題時他們是不會關心對方是如何計算怎樣開采金礦的，因為他們知道亥鸠，國王只會選擇兩個人中的一個作為最后方案璧眠，另一個人的方案并不會得到實施，因此一個人的決定對另一個人的決定是沒有影響的读虏。我們把這種一個母問題在對子問題選擇時，當前被選擇的子問題兩兩互不影響的情況叫做“子問題獨立”袁滥。
這就是動態(tài)規(guī)劃盖桥，具有“最優(yōu)子結構”、“子問題重疊”题翻、“邊界”和“子問題獨立”揩徊，當你發(fā)現(xiàn)你正在思考的問題具備這四個性質的話腰鬼，那么恭喜你，你基本上已經(jīng)找到了動態(tài)規(guī)劃的方法塑荒。
有了上面的這幾點熄赡，我們就可以寫出動態(tài)規(guī)劃的轉移方程式，現(xiàn)在我們來寫出對應這個問題的方程式齿税，如果用gold[mineNum]表示第mineNum個金礦能夠挖出的金子數(shù)彼硫，用peopleNeeded[mineNum]表示挖第mineNum個金礦需要的人數(shù)，用函數(shù)f(people,mineNum)表示當有people個人和編號為0凌箕、1拧篮、2、3牵舱、……串绩、mineNum的金礦時能夠得到的最大金子數(shù)的話，f(people,mineNum)等于什么呢芜壁？或者說f(people,mineNum)的轉移方程是怎樣的呢礁凡？
答案是：
當mineNum = 0且people >= peopleNeeded[mineNum]時 f(people,mineNum) = gold[mineNum]
當mineNum = 0且people < peopleNeeded[mineNum]時 f(people,mineNum) = 0
當mineNum != 0時 f(people,mineNum) = f(people-peopleNeeded[mineNum], mineNum-1) + gold[mineNum]與f(people, mineNum-1)中的較大者，前兩個式子對應動態(tài)規(guī)劃的“邊界”慧妄，后一個式子對應動態(tài)規(guī)劃的“最優(yōu)子結構”請讀者弄明白后再繼續(xù)往下看顷牌。
----第二節(jié)----動態(tài)規(guī)劃的優(yōu)點--------
現(xiàn)在我假設讀者你已經(jīng)搞清楚了為什么動態(tài)規(guī)劃是正確的方法，但是我們?yōu)槭裁葱枰褂脛討B(tài)規(guī)劃呢腰涧？請先繼續(xù)欣賞這個故事：
國王得知他的兩個手下使用了和他相同的方法去解決交代給他們的問題后韧掩，不但沒有認為他的兩個大臣在偷懶，反而很高興窖铡，因為他知道疗锐，他的大臣必然會找更多的人一起解決這個問題，而更多的人會找更更多的人费彼，這樣他這個聰明的方法就會在不經(jīng)意間流傳開來滑臊，而全國人民都會知道這個聰明的方法是他們偉大的國王想出來的，你說國王能不高興嗎箍铲？
但是國王也有一些擔憂雇卷，因為他實在不知道這個“工程”要動用到多少人來完成，如果幫助他解決這個問題的人太多的話那么就太勞民傷財了颠猴」鼗“會不會影響到今年的收成呢？”國王在心里想著這個問題翘瓮，于是他請來了整個國家里唯一的兩個數(shù)學天才贮折，一個叫做小天，另一個叫做小才资盅。
國王問小天：“小天啊调榄，我發(fā)覺這個問題有點嚴重踊赠，我知道其實這可以簡單的看成一個組合問題，也就是從十個金礦中選取若干個金礦進行開采每庆，看看哪種組合得到的金子最多筐带，也許用組合方法會更好一些。你能告訴我一共有多少種組合情況嗎缤灵？”
“國王陛下伦籍，如果用組合方法的話一共要考慮2的10次方種情況，也就是1024種情況凤价「胝澹”小天思考了一會回答到。
“嗯……利诺，如果每一種情況我交給一個人去計算能得到的金子數(shù)的話富蓄，那我也要1024個人，其實還是挺多的慢逾×⒈叮”國王好像再次感覺到了自己的方法是正確的。
國王心理期待著小才能夠給它一個更好的答案侣滩，問到：“小才啊口注，那么你能告訴我用我的那個方法總共需要多少人嗎？其實君珠，我也計算過寝志，好像需要的人數(shù)是1+2+4+8+16+32+64+……，畢竟每一個人的確都需要找另外兩個人來幫助他們……”
不辜負國王的期待策添，小才微笑著說到：“親愛的國王陛下材部，其實我們并不需要那么多人，因為有很多問題其實是相同的唯竹，而我們只需要為每一個不同的問題使用一個人力便可椭坚≌悖”
國王高興的問到：“此話如何講？”
“打個比方舷蟀，如果有一個人需要知道1000個人和3個金礦可以開采出多少金子骄蝇，同時另一個人也需要知道1000個人和3個金礦可以開采出多少金子的話候醒，那么他們可以去詢問相同的一個人假颇，而不用各自找不同的人浪費人力了歹啼。”
國王思考著說到：“嗯晋涣，很有道理仪媒，如果問題是一樣的話那么就不需要去詢問兩個不同的人了，也就是說一個不同的問題僅需要一個人力姻僧，那么一共有多少個不同的問題呢规丽？”
“因為每個問題的人數(shù)可以從0取到10000，而金礦數(shù)可以從0取到10撇贺，所以最多大約有10000 * 10 等于100000個不同的問題赌莺。” 小才一邊算著一邊回答松嘶。
“什么艘狭？十萬個問題？十萬個人力翠订？”國王有點失望巢音。
“請國王放心，事實上我們需要的人力遠遠小于這個數(shù)的尽超，因為不是每一個問題都會遇到官撼，也許我們僅需要一、兩百個人力就可以解決這個問題了似谁，這主要和各個金礦所需要的人數(shù)有關傲绣。” 小才立刻回答到巩踏。
故事的最后秃诵，自然是國王再一次向他的臣民們證明了他是這個國家里最聰明的人，現(xiàn)在我們通過故事的第二部分來考慮動態(tài)規(guī)劃的另外兩個思考點塞琼。
思考動態(tài)規(guī)劃的第五點----做備忘錄：
正如上面所說的一樣菠净，當我們遇到相同的問題時，我們可以問同一個人彪杉。講的通俗一點就是毅往，我們可以把問題的解放在一個變量中，如果再次遇到這個問題就直接從變量中獲得答案在讶，因此每一個問題僅會計算一遍煞抬，如果不做備忘的話，動態(tài)規(guī)劃就沒有任何優(yōu)勢可言了构哺。
思考動態(tài)規(guī)劃的第六點----時間分析：
正如上面所說革答，如果我們用窮舉的方法，至少需要2^n個常數(shù)時間曙强，因為總共有2^n種情況需要考慮残拐，如果在背包問題中，包的容量為1000碟嘴，物品數(shù)為100溪食，那么需要考慮2^100種情況,這個數(shù)大約為10的30次方。
而如果用動態(tài)規(guī)劃娜扇，最多大概只有1000*100 = 100000個不同的問題错沃，這和10的30次方比起來優(yōu)勢是很明顯的栅组。而實際情況并不會出現(xiàn)那么多不同的問題，比如在金礦模型中枢析，如果所有的金礦所需人口都是1000個人玉掸，那么問題總數(shù)大約只有100個。
非正式地醒叁，我們可以很容易得到動態(tài)規(guī)劃所需時間司浪，如果共有questionCount個相同的子問題，而每一個問題需要面對chooseCount種選擇時把沼，我們所需時間就為questionCount * chooseCount個常數(shù)啊易。在金礦模型中，子問題最多有大概people * n 個(其中people是用于開采金礦的總人數(shù)饮睬，n是金礦的總數(shù))租谈，因此questionCount = people * n，而就像國王需要考慮是采用左部下的結果還是采用右部下的結果一樣续捂，每個問題面對兩個選擇垦垂，因此chooseCount = 2,所以程序運行時間為 T = O(questionCount * chooseCount) =O(people * n)，別忘了實際上需要的時間小于這個值牙瓢，根據(jù)所遇到的具體情況有所不同劫拗。
這就是動態(tài)規(guī)劃的魔力，它減少了大量的計算矾克，因此我們需要動態(tài)規(guī)劃页慷！
----第三節(jié)----動態(tài)規(guī)劃的思考角度----------
那么什么是動態(tài)規(guī)劃呢？我個人覺得胁附，如果一個解決問題的方法滿足上面六個思考點中的前四個酒繁，那么這個方法就屬于動態(tài)規(guī)劃。而在思考動態(tài)規(guī)劃方法時控妻，后兩點同樣也是需要考慮的州袒。
面對問題要尋找動態(tài)規(guī)劃的方法，首先要清楚一點弓候，動態(tài)規(guī)劃不是算法郎哭，它是一種方法，它是在一件事情發(fā)生的過程中尋找最優(yōu)值的方法菇存，因此夸研，我們需要對這件事情所發(fā)生的過程進行考慮。而通常我們從過程的最后一步開始考慮依鸥，而不是先考慮過程的開始亥至。
打個比方，上面的挖金礦問題，我們可以認為整個開采過程是從西至東進行開采的（也就是從第0座開始）姐扮，那么總有面對最后一座金礦的時候（第9座）絮供，對這座金礦不外乎兩個選擇，開采與不開采茶敏，在最后一步確定時再去確定倒數(shù)第二步杯缺，直到考慮第0座金礦（過程的開始）。
而過程的開始睡榆，也就是考慮的最后一步，就是邊界袍榆。
因此在遇到一個問題想用動態(tài)規(guī)劃的方法去解決時胀屿，不妨先思考一下這個過程是怎樣的，然后考慮過程的最后一步是如何選擇的包雀，通常我們需要自己去構造一個過程宿崭，比如后面的練習。
----第四節(jié)----總結-------
那么遇到問題如何用動態(tài)規(guī)劃去解決呢才写？根據(jù)上面的分析我們可以按照下面的步驟去考慮：
1葡兑、構造問題所對應的過程。
2赞草、思考過程的最后一個步驟讹堤，看看有哪些選擇情況。
3厨疙、找到最后一步的子問題洲守，確保符合“子問題重疊”，把子問題中不相同的地方設置為參數(shù)沾凄。
4梗醇、使得子問題符合“最優(yōu)子結構”。
5撒蟀、找到邊界叙谨，考慮邊界的各種處理方式。
6保屯、確保滿足“子問題獨立”手负，一般而言，如果我們是在多個子問題中選擇一個作為實施方案配椭，而不會同時實施多個方案虫溜，那么子問題就是獨立的。
7股缸、考慮如何做備忘錄衡楞。
8、分析所需時間是否滿足要求。
9瘾境、寫出轉移方程式歧杏。
----第五節(jié)----練習-------
題目一：買書
有一書店引進了一套書，共有3卷迷守，每卷書定價是60元犬绒，書店為了搞促銷，推出一個活動兑凿，活動如下：
如果單獨購買其中一卷凯力，那么可以打9.5折。
如果同時購買兩卷不同的礼华，那么可以打9折咐鹤。
如果同時購買三卷不同的，那么可以打8.5折圣絮。
如果小明希望購買第1卷x本祈惶，第2卷y本，第3卷z本扮匠，那么至少需要多少錢呢捧请？（x、y棒搜、z為三個已知整數(shù)）力麸。
當然氧吐，這道題完全可以不用動態(tài)規(guī)劃來解末盔，但是現(xiàn)在我們是要學習動態(tài)規(guī)劃筑舅，因此請想想如何用動態(tài)規(guī)劃來做？
答案：
1陨舱、過程為一次一次的購買游盲，每一次購買也許只買一本（這有三種方案）莺奔，或者買兩本（這也有三種方案）欣范，或者三本一起買（這有一種方案），最后直到買完所有需要的書蛙卤。
2已维、最后一步我必然會在7種購買方案中選擇一種占婉，因此我要在7種購買方案中選擇一個最佳情況逆济。
3岛马、子問題是啦逆，我選擇了某個方案后伞矩，如何使得購買剩余的書能用最少的錢？并且這個選擇不會使得剩余的書為負數(shù)夏志。母問題和子問題都是給定三卷書的購買量乃坤，求最少需要用的錢，所以有“子問題重疊”，問題中三個購買量設置為參數(shù)侥袜，分別為i蝌诡、j、k枫吧。
4浦旱、的確符合。
5九杂、邊界是一次購買就可以買完所有的書颁湖，處理方式請讀者自己考慮。
6例隆、每次選擇最多有7種方案甥捺，并且不會同時實施其中多種，因此方案的選擇互不影響镀层，所以有“子問題獨立”镰禾。
7、我可以用minMoney[j][k]來保存購買第1卷i本唱逢，第2卷j本吴侦，第3卷k本時所需的最少金錢。
8坞古、共有x * y * z 個問題备韧，每個問題面對7種選擇，時間為：O( x * y * z * 7) =?? O( x * y * z )痪枫。
9织堂、用函數(shù)MinMoney(i,j,k)來表示購買第1卷i本，第2卷j本奶陈，第3卷k本時所需的最少金錢易阳，那么有：
MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分別為對應的7種方案使用的最少金錢：
s1 = 60 * 0.95 + MinMoney(i-1,j,k)
s2 = 60 * 0.95 + MinMoney(i,j-1,k)
s3 = 60 * 0.95 + MinMoney(i,j,k-1)
s4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k)
s5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
s6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
s7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1)
----第六節(jié)----代碼參考------
下面提供金礦問題的程序源代碼幫助讀者理解，并提供測試數(shù)據(jù)給大家練習吃粒。
輸入文件名為“beibao.in”闽烙，因為這個問題實際上就是背包問題，所以測試數(shù)據(jù)文件名就保留原名吧声搁。
輸入文件第一行有兩個數(shù)黑竞，第一個是國王可用用來開采金礦的總人數(shù)，第二個是總共發(fā)現(xiàn)的金礦數(shù)疏旨。
輸入文件的第2至n+1行每行有兩個數(shù)很魂，第i行的兩個數(shù)分別表示第i-1個金礦需要的人數(shù)和可以得到的金子數(shù)。
輸出文件僅一個整數(shù)檐涝，表示能夠得到的最大金子數(shù)遏匆。
輸入樣例：
100 5
77 92
22 22
29 87
50 46
99 90
輸出樣例：
133
http://blog.csdn.net/woshioosm/article/details/7438834 csdn原文
