声明:本文参考了Hawstein的文章,我觉得写的非常好,可以好好研读一下。
原文链接http://hawstein.com/posts/dp-novice-to-advanced.html
动态规划,Dynamic Programming,这里的programming并不是我们所理解的编程,计算机程序,而是表格的意思。
在我们开始学习的时候,就会理解为什么这么说了。
动态规划通常基于一个递推公式以及若干个初始状态,将一个大问题分解为子问题,当前子问题的解由上一个子问题的解推出。
很多问题我们选择动态规划是因为即使他有其他的方法,譬如回溯法,暴力求解,但是动态规划只需要多项式时间复杂度解决问题。
原文用了这么一个例子,
我么手中有1元,3元,5元的硬币,如何用最少的硬币来凑够11元。
类似数学归纳法,分治法,我们总是考虑一些理解起来比较容易,看上去比较直观的情况,然后采用化归的思想,先去考虑一些规模较小的问题,如何去解决。
首先,我们来看一个看似滑稽但基础的情况,凑够0元。
很明显,我们手里只有1元,3元,5元,并没有0元面值的,那么至少需要0个硬币。
当我们要凑够1元的时候,我们只需要1个1元的硬币即可。但是从一个奇特的角度想,当凑够1元时,还剩下0元,归纳为解决凑0元的问题,再需要0个硬币。
当我们要凑够2元的时候,看看手里,只有1元硬币可以用,我们拿起一个1元先凑1元,然后还差1元,归纳为解决凑1元的问题,然后再拿1元就好。
当我们要凑够3元的时候,这时候就要考虑我们所要面值了,有两种情况,
我们继续使用1元的硬币,先凑1元,那么还需要两元,此时其实就时相当于归纳为解决凑2元的问题了,回去看就好了。
我们使用3元的硬币,此时拿起一个3元硬币,那么我们还需要再凑0元,又归纳为凑0元的问题。
考虑这两种情况,我们的问题是最少,那么很明显就是选择1个3元硬币方案了。
从数学的角度去看,我们来抽象归纳一下上面的叙述。
记d(m)=n:表示凑够m元最少需要n个硬币。
那么有:
很容易我们就可以归结出来:
根据这一条,我们就很容易写出代码了: