问题标题: 动态规划讲义

对于动态规划，每一个刚接触的人都须要一段时间来理解，特别是第一次接触的时候总是想不通为什么这样的方法可行，这篇文章就是为了帮助大家理解动态规划，并通过解说主要的01背包问题来引导读者怎样去思考动态规划。本文力求通俗易懂，无异**，不让读者感到迷惑，引导读者去思考，所以假设你在阅读中发现有不通顺的地方，让你产生错误理解的地方，让你难得读懂的地方，请跟贴指出，谢谢！ 

----第一节----初识动态规划--------

       经典的01背包问题是这种：
       有一个包和n个物品，包的容量为m，每一个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，可以得到的最大价值是多少？[对于每一个物品不可以取多次，最多仅仅能取一次，之所以叫做01背包，0表示不取，1表示取]

       为了用一种生动又更形象的方式来解说此题，我把此题用还有一种方式来描写叙述，例如以下：

       有一个国家，全部的国民都很老实憨厚，某天他们在自己的国家发现了十座金矿，而且这十座金矿在地图上排成一条直线，国王知道这个消息后很高兴，他希望可以把这些金子都挖出来造福国民，首先他把这些金矿依照在地图上的位置从西至东进行编号，依次为0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去对每一座金矿进行勘測，以便知道挖取每一座金矿须要多少人力以及每座金矿可以挖出多少金子，然后动员国民都来挖金子。

       题目补充1：挖每一座金矿须要的人数是固定的，多一个人少一个人都不行。国王知道每一个金矿各须要多少人手，金矿i须要的人数为peopleNeeded。
       题目补充2：每一座金矿所挖出来的金子数是固定的，当第i座金矿有peopleNeeded人去挖的话，就一定能恰好挖出gold个金子。否则一个金子都挖不出来。
       题目补充3：开採一座金矿的人完毕开採工作后，他们不会再次去开採其他金矿，因此一个人最多仅仅能使用一次。
       题目补充4：国王在全国范围内仅招募到了10000名愿意为了国家去挖金子的人，因此这些人可能不够把全部的金子都挖出来，可是国王希望挖到的金子越多越好。
       题目补充5：这个国家的每个人都非常老实（包含国王），不会私吞不论什么金子，也不会弄虚作假，不会说谎话。
       题目补充6：有非常多人拿到这个题后的第一反应就是对每个金矿求出平均每个人能挖出多少金子，然后从高到低进行选择，这里要强调这样的方法是错的，假设你也是这样想的，请考虑背包模型，当有一个背包的容量为10，共同拥有3个物品，体积各自是3、3、5，价值各自是6、6、9，那么你的方法取到的是前两个物品，总价值是12，但明显最大值是后两个物品组成的15。
       题目补充7：我们仅仅须要知道最多能够挖出多少金子就可以，而不用关心哪些金矿挖哪些金矿不挖。

       那么，国王到底怎样知道在仅仅有10000个人的情况下最多能挖出多少金子呢？国王是怎样思考这个问题的呢？

       国王首先来到了第9个金矿的所在地（注意，第9个就是最后一个，由于是从0開始编号的，最西边的那个金矿是第0个），他的臣子告诉他，假设要挖取第9个金矿的话就须要1500个人，而且第9个金矿能够挖出8888个金子。听到这里国王哈哈大笑起来，由于原先他以为要知道十个金矿在仅有10000个人的情况下最多能挖出多少金子是一件非常难思考的问题，可是，就在刚才听完他的臣子所说的那句话时，国王已经知道总共最多能挖出多少金子了，国王是怎样在不了解其他金矿的情况下知道最多能挖出多少金子的呢？他的臣子们也不知道这个谜，因此他的臣子们就问他了：“最聪明的国王陛下，我们都没有告诉您其他金矿的情况，您是怎样知道终于答案的呢？”

       得意的国王笑了笑，然后把他最得意的“左、右手”叫到跟前，说到：“我并不须要考虑终于要挖哪些金矿才干得到最多的金子，我仅仅须要考虑我面前的这座金矿就能够了，对于我面前的这座金矿不外乎仅有两种选择，要么挖，要么不挖，对吧？”

       “当然，当然”大臣们回答倒。

       国王继续说道：“假设我挖取第9座金矿的话那么我如今就能获得8888个金子，而我将用去1500个人，那么我还剩下8500个人。我亲爱的左部下，假设你告诉我当我把全部剩下的8500个人和全部剩下的其他金矿都交给你去开採你最多能给我挖出多少金子的话，那么我不就知道了在第9个金矿一定开採的情况下所能得到的最大金币数吗？”

       国王的左部下听后回答道：“国王陛下，您的意思是假设我能用8500个人在其他金矿最多开採出x个金币的话，那您一共就行获得 x + 8888个金子，对吗？”

       “是啊，是啊……假设第9座金矿一定开採的话……”大臣们点头说到。

       国王笑着继续对着他的右部下说到：“亲爱的右部下，或许我并不打算开採这第9座金矿，那么我依旧拥有10000个人，假设我把这10000个人和剩下的金矿都给你的话，你最多能给我挖出多少个金子呢？”

       国王的右部下聪明地说道：“尊敬的国王陛下，我明确您的意思了，假设我回答最多能购开採出y个金币的话，那您就能够在y和x+8888之间选择一个较大者，而这个较大者就是终于我们能获得的最大金币数，您看我这样理解对吗？”


       国王笑得更灿烂了，问他的左部下：“那么亲爱的左部下，我给你8500个人和其余金矿的话你能告诉我最多能挖出多少金子吗？”

       “请您放心，这个问题难不倒我”。左部下向国王打包票说到。

       国王高兴地继续问他的右部下：“那右部下你呢，假设我给你10000个人和其余金矿的话你能告诉我最多能挖出多少金子吗？”

       “当然能了！交给我吧！”右部下同左部下一样自信地回答道。

       “那就拜托给你们两位了，如今我要回到我那舒适的王宫里去享受了，我期待着你们的答复。”国王说完就開始动身回去等消息了，他是多么地相信他的两个大臣可以给他一个准确的答复，由于国王事实上知道他的两位大臣要比他聪明得多。

       故事发展到这里，你是否在想国王的这两个大臣又是怎样找到让国王惬意的答案的呢？他们为什么可以如此自信呢？其实他们的确比国王要聪明一些，由于他们从国王的身上学到了一点，就是这一点让他们充满了自信。

       国王走后，国王的左、右部下来到了第8座金矿，早已在那里等待他们的金矿勘測兵向两位大臣报道：“聪明的两位大臣，您们好，第8座金矿须要1000个人才干开採，能够获得7000个金子”。

       由于国王仅给他的左部下8500个人，所以国王的左部下叫来了两个人，对着当中一个人问到：“假设我给你7500个人和除了第8、第9的其他全部金矿的话，你能告诉我你最多能挖出多少金子吗？”

       然后国王的左部下继续问还有一个人：“假设我给你8500个人和除了第8、第9的其他全部金矿的话，你能告诉我你最多能挖出多少金子吗？”

       国王的左部下在心里想着：“假设他们俩都能回答我的问题的话，那国王交给我的问题不就攻克了吗？哈哈哈！”

       由于国王给了他的右部下10000个人，所以国王的右部下相同也叫来了两个人，对着当中一个人问：“假设我给你9000个人和除了第8、第9的其他全部金矿的话，你能告诉我你最多能挖出多少金子吗？”

       然后国王的右部下继续问他叫来的还有一个人：“假设我给你10000个人和除了第8、第9的其他全部金矿的话，你能告诉我你最多能挖出多少金子吗？”

       此时，国王的右部下同左部下一样，他们都在为自己如此聪明而感到满足。

       当然，这四个被叫来的人相同自信地回答没有问题，由于他们相同地从这两个大臣身上学到了相同的一点，而两位自觉得自己一样非常聪明的大臣得意地笑着回到了他们的府邸，等着别人回答他们提出来的问题，如今你知道了这两个大臣是怎样解决国王交待给他们的问题了吗？

       那么你觉得被大臣叫去的那四个人又是怎么完毕大臣交给他们的问题的呢？答案当然是他们找到了另外八个人！

       没用多少功夫，这个问题已经在全国传开了，很多其它人的人找到了更很多其它的人来解决问题，而有些人却不须要去另外找两个人帮他，哪些人不须要别人的帮助就能够回答他们的问题呢？

       非常明显，当被问到给你z个人和仅有第0座金矿时最多能挖出多少金子时，就不须要别人的帮助，由于你知道，假设z大于等于挖取第0座金矿所须要的人数的话，那么挖出来的最多金子数就是第0座金矿可以挖出来的金子数，假设这z个人不够开採第0座金矿，那么能挖出来的最多金子数就是0，由于这唯一的金矿不够人力去开採。让我们为这些不须要别人的帮助就行准确地得出答案的人们鼓掌吧，这就是传说中的底层劳动人民！

       故事说到这里先暂停一下，我们如今又一次来分析一下这个故事，让我们对动态规划有个理**认识。

       子问题：
       国王须要依据两个大臣的答案以及第9座金矿的信息才干推断出最多可以开採出多少金子。为了解决自己面临的问题，他须要给别人制造另外两个问题，这两个问题就是子问题。

       思考动态规划的第一点----最优子结构：
       国王相信，仅仅要他的两个大臣可以回答出正确的答案（对于考虑可以开採出的金子数，最多的也就是最优的同一时候也就是正确的），再加上他的聪明的推断就一定能得到终于的正确答案。我们把这样的子问题最优时母问题通过优化选择后一定最优的情况叫做“最优子结构”。

       思考动态规划的第二点----子问题重叠：
       实际上国王也好，大臣也好，全部人面对的都是相同的问题，即给你一定数量的人，给你一定数量的金矿，让你求出可以开採出来的最多金子数。我们把这样的母问题与子问题本质上是同一个问题的情况称为“子问题重叠”。然而问题中出现的不同点往往就是被子问题之间传递的參数，比方这里的人数和金矿数。

       思考动态规划的第三点----边界：
       想想假设不存在前面我们提到的那些底层劳动者的话这个问题能解决吗？永远都不可能！我们把这样的子问题在一定时候就不再须要提出子子问题的情况叫做边界，没有边界就会出现**循环。

       思考动态规划的第四点----子问题**：
       要知道，当国王的两个大臣在思考他们自己的问题时他们是不会关心对方是如何计算如何开採金矿的，由于他们知道，国王仅仅会选择两个人中的一个作为最后方案，还有一个人的方案并不会得到实施，因此一个人的决定对还有一个人的决定是没有影响的。我们把这样的一个母问题在对子问题选择时，当前被选择的子问题两两互不影响的情况叫做“子问题**”。


       这就是动态规划，具有“最优子结构”、“子问题重叠”、“边界”和“子问题**”，当你发现你正在思考的问题具备这四个**质的话，那么恭喜你，你基本上已经找到了动态规划的方法。

       有了上面的这几点，我们就行写出动态规划的转移方程式，如今我们来写出相应这个问题的方程式，假设用gold[mineNum]表示第mineNum个金矿可以挖出的金子数，用peopleNeeded[mineNum]表示挖第mineNum个金矿须要的人数，用函数f(people,mineNum)表示当有people个人和编号为0、1、2、3、……、mineNum的金矿时可以得到的最大金子数的话，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)中的较大者，前两个式子相应动态规划的“边界”，后一个式子相应动态规划的“最优子结构”请读者弄明确后再继续往下看。






----第二节----动态规划的长处--------

       如今我如果读者你已经搞清楚了为什么动态规划是正确的方法，可是我们为什么须要使用动态规划呢？请先继续赞赏这个故事：

       国王得知他的两个手下使用了和他同样的方法去解决交代给他们的问题后，不但没有觉得他的两个大臣在偷懒，反而非常高兴，由于他知道，他的大臣必定会找很多其它的人一起解决问题，而很多其它的人会找更很多其它的人，这样他这个聪明的方法就会在不经意间流传开来，而全国人民都会知道这个聪明的方法是他们伟大的国王想出来的，你说国王能不高兴吗？

       可是国王也有一些担忧，由于他实在不知道这个“project”要动用到多少人来完毕，假设帮助他解决问题的人太多的话那么就太劳民伤財了。“会不会影响到今年的收成呢？”国王在心里想着这个问题，于是他请来了整个国家里唯一的两个数学天才，一个叫做小天，还有一个叫做小才。

       国王问小天：“小天啊，我发觉这个问题有点严重，我知道事实上这能够简单的看成一个组合问题，也就是从十个金矿中选取若干个金矿进行开採，看看哪种组合得到的金子最多，或许用组合方法会更好一些。你能告诉我一共同拥有多少种组合情况吗？”

       “国王陛下，假设用组合方法的话一共要考虑2的10次方种情况，也就是1024种情况。”小天思考了一会回答到。

       “嗯……，假设每一种情况我交给一个人去计算能得到的金子数的话，那我也要1024个人，事实上还是挺多的。”国王好像再次感觉到了自己的方法是正确的。

       国王心理期待着小才可以给它一个更好的答案，问到：“小才啊，那么你能告诉我用我的那个方法总共须要多少人吗？事实上，我也计算过，好像须要的人数是1+2+4+8+16+32+64+……，毕竟每个人的确都须要找另外两个人来帮助他们……”

       不辜负国王的期待，小才微笑着说到：“亲爱的国王陛下，事实上我们并不须要那么多人，由于有非常多问题事实上是同样的，而我们仅仅须要为每个不同的问题使用一个人力便可。”

       国王高兴的问到：“此话怎样讲？”

       “打个例如，假设有一个人须要知道1000个人和3个金矿能够开採出多少金子，同一时候还有一个**须要知道1000个人和3个金矿能够开採出多少金子的话，那么他们能够去询问同样的一个人，而不用各自找不同的人浪费人力了。”

       国王思考着说到：“嗯，非常有道理，假设问题是一样的话那么就不须要去询问两个不同的人了，也就是说一个不同的问题仅须要一个人力，那么一共同拥有多少个不同的问题呢？”   

       “由于每一个问题的人数能够从0取到10000，而金矿数能够从0取到10，所以最多大约有10000 * 10 等于100000个不同的问题。” 小才一边算着一边回答。

       “什么？十万个问题？十万个人力？”国王有点失望。

       “请国王放心，其实我们须要的人力远远小于这个数的，由于不是每个问题都会遇到，或许我们仅须要一、两百个人力就能够解决问题了，这主要和各个金矿所须要的人数有关。” 小才立马回答到。

       故事的最后，自然是国王再一次向他的臣民们证明了他是这个国家里最聪明的人，如今我们通过故事的第二部分来考虑动态规划的另外两个思考点。

       思考动态规划的第五点----做备忘录：
       正如上面所说的一样，当我们遇到同样的问题时，我们能够问同一个人。讲的通俗一点就是，我们能够把问题的解放在一个变量中，假设再次遇到这个问题就直接从变量中获得答案，因此每个问题仅会计算一遍，假设不做备忘的话，动态规划就没有不论什么优势可言了。             

       思考动态规划的第六点----时间分析：
       正如上面所说，假设我们用穷举的方法，至少须要2^n个常数时间，由于总共同拥有2^n种情况须要考虑，假设在背包问题中，包的容量为1000，物品数为100，那么须要考虑2^100种情况,这个数大约为10的30次方。

       而假设用动态规划，最多大概仅仅有1000*100 = 100000个不同的问题，这和10的30次方比起来优势是非常明显的。而实际情况并不会出现那么多不同的问题，比方在金矿模型中，假设全部的金矿所需人口都是1000个人，那么问题总数大约仅仅有100个。

       非正式地，我们能够非常easy得到动态规划所需时间，假设共同拥有questionCount个同样的子问题，而每个问题须要面对chooseCount种选择时，我们所需时间就为questionCount * chooseCount个常数。在金矿模型中，子问题最多有大概people * n 个(当中people是用于开採金矿的总人数，n是金矿的总数)，因此questionCount = people * n，而就像国王须要考虑是採用左部下的结果还是採用右部下的结果一样，每个问题面对两个选择，因此chooseCount = 2,所以程序执行时间为 T = O(questionCount * chooseCount) =O(people * n)，别忘了实际上须要的时间小于这个值，依据所遇到的详细情况有所不同。

       这就是动态规划的魔力，它降低了大量的计算，因此我们须要动态规划！






----第三节----动态规划的思考角度----------

       那么什么是动态规划呢？我个人认为，假设一个解决这个问题的方法满足上面六个思考点中的前四个，那么这种方法就属于动态规划。而在思考动态规划方法时，后两点相同也是须要考虑的。

       面对问题要寻找动态规划的方法，首先要清楚一点，动态规划不是算法，它是一种方法，它是在一件事情发生的过程中寻找最优值的方法，因此，我们须要对这件事情所发生的过程进行考虑。而通常我们从过程的最后一步開始考虑，而不是先考虑过程的開始。

       打个例如，上面的挖金矿问题，我们能够觉得整个开採过程是从西至东进行开採的（也就是从第0座開始），那么总有面对最后一座金矿的时候（第9座），对这座金矿不外乎两个选择，开採与不开採，在最后一步确定时再去确定倒数第二步，直到考虑第0座金矿（过程的開始）。

       而过程的開始，也就是考虑的最后一步，就是边界。

       因此在遇到一个问题想用动态规划的方法去解决时，最好还是先思考一下这个过程是如何的，然后考虑过程的最后一步是如何选择的，通常我们须要自己去构造一个过程，比方后面的练习。







----第四节----总结-------

       那么遇到问题怎样用动态规划去解决呢？依据上面的分析我们能够依照以下的步骤去考虑：

       1、构造问题所相应的过程。
       2、思考过程的最后一个步骤，看看有哪些选择情况。
       3、找到最后一步的子问题，确保符合“子问题重叠”，把子问题中不同样的地方设置为參数。
       4、使得子问题符合“最优子结构”。
       5、找到边界，考虑边界的各种处理方式。
       6、确保满足“子问题**”，一般而言，假设我们是在多个子问题中选择一个作为实施方案，而不会同一时候实施多个方案，那么子问题就是**的。
       7、考虑怎样做备忘录。
       8、分析所需时间是否满足要求。
       9、写出转移方程式。





----第五节----练习-------

       题目一：买书
       有一书店引进了一套书，共同拥有3卷，每卷书定价是60元，书店为了搞促销，推出一个活动，活动例如以下：

       假设单独购买当中一卷，那么能够打9.5折。
       假设同一时候购买两卷不同的，那么能够打9折。
       假设同一时候购买三卷不同的，那么能够打8.5折。

       假设小明希望购买第1卷x本，第2卷y本，第3卷z本，那么至少须要多少钱呢？（x、y、z为三个已知整数）。

       当然，这道题全然能够不用动态规划来解，可是如今我们是要学习动态规划，因此请想想怎样用动态规划来做？

       答案：

       1、过程为一次一次的购买，每一次购买或许仅仅买一本（这有三种方案），或者买两本（这也有三种方案），或者三本一起买（这有一种方案），最后直到买全然部须要的书。
       2、最后一步我必定会在7种购买方案中选择一种，因此我要在7种购买方案中选择一个最佳情况。
       3、子问题是，我选择了某个方案后，怎样使得购买剩余的书能用最少的钱？而且这个选择不会使得剩余的书为负数。母问题和子问题都是给定三卷书的购买量，求最少须要用的钱，所以有“子问题重叠”，问题中三个购买量设置为參数，分别为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、用函数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)





----第六节----代码參考------


       以下提供金矿问题的程序源码帮助读者理解，并提供測试数据给大家练习。

       输入文件名称为“beibao.in”，由于这个问题实际上就是背包问题，所以測试数据文件名称就保留原名吧。
       输入文件第一行有两个数，第一个是国王可用用来开採金矿的总人数，第二个是总共发现的金矿数。
       输入文件的第2至n+1行每行有两个数，第i行的两个数分别表示第i-1个金矿须要的人数和能够得到的金子数。

       输出文件仅一个整数，表示可以得到的最大金子数。

       输入例子：
       100 5
       77 92
       22 22
       29 87
       50 46
       99 90

       输出例子：
       133

望采纳！