文档介绍：动态规划(dynamicprogramming)核心最优子结构,边界,状态转移公式(记住已经解决过的子问题的解)经典问题爬楼梯国王的金矿爬楼梯有一个n阶的楼梯,松鼠每一步可以选择走一步或者两步,那么到达第m阶的时候,总共有多少种走法?(n>0,0<m≤n)以第9层为例。要到第九层,只有两种情况,也就是从第八层到第九层,或者第七层到第九层。只要分别知道到达第七层和到达第八层的情况总数就可以知道了,也就是 F(9)=F(8)+F(7)那么可以很容易想到递归的结构,那么递归下去总会得到 F(3)=F(2)+F(1)而到达第一层只有一种情况,到达第二层只有两种情况,也就是 F(1)=1,F(2)=2到这里为止,动态规划的三个要素就都有了。最优子结构:F(7)和F(8)就是F(9)的最优子结构,其他类似边界:这个题目的边界就是F(1)和F(2),边界已知状态转移方程:F(n)=F(n-1)+F(n-2)求解方式上面的方法很容易写出代码求解,但是不同方法的效率相差很大。递归备忘录算法递归上面的状态转移方程本身就是递归,F(n)=F(n-1)+F(n-2),代码上很容易实现,但是问题在于如果直接算F(n),那么从F(3)到F(n-1)都会重复计算,当n变大的时候,效率下降特别快。这是因为直接计算的时候是自顶向下,而且没有存储中间的计算结果。备忘录算法备忘录算法其实就是递归的改良版,实现自下向上的计算方式,其实也就是从原点位置建立起整个表,然后再计算多少次都只是从表里取数值罢了。也就是说先算F(3)=F(2)+F(1),得到F(3),再算F(4)…这样会增加空间复杂度,但是极大的降低了时间复杂度,当然,只是在这个问题中,算法本身没有好坏,只是应用场景不同国王的金矿有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人(第二集说的是1000人,这里改动一下)。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?看过第一个问题,应该尽快把这个问题类比过去。先说方法,再解惑。想的突破口还是一样,由具体的例子再推广。我们要求10个人挖5个金矿利益最大化,其实只有两种情况,挖不挖第五个金矿?有可能10个人去挖4个金矿就已经利益最大了,也有可能分出几个人去挖第五个金矿,剩下的人去挖前4个,综合起来的利益比10个人去挖四个金矿的利益更大。我当时看的时候感觉很疑惑,这个行不通啊,因为不管哪种情况人都不够啊,但是再问一遍这个问题,也就清楚了,10个人或者剩下的人去挖前4个金矿的话,也只有两种情况,看挖不挖第四个,那么无形中就有了转移方程,但这个是二维的,因为人数和金矿数都会有影响。那么状态转移方程就是 F(n,m)=MAX(F(n-1,m),F(n-1,m-NUM(n))+F(n,NUM(n)))自然最优子结构也知道了n是金矿数量,m是工人数量,NUM(n)是第n个金矿需要的工人数量,因为我们算的是5个金矿10个工人的利益最大化,所以这些顺序就不重要了。