我们为什么需要使用动态规划呢？请先继续欣赏这个故事：

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

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

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

“国王陛下，如果用组合方法的话一共要考虑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个。

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

这就是动态规划的魔力，它减少了大量的计算，因此我们需要动态规划！