动态规划

动态规划（dynamicprogramming）核心最优子结构，边界，状态转移公式（记住已经解决过的子问题的解）经典问题•爬楼梯•国王的金矿爬楼梯有一个n阶的楼梯，松鼠每一步可以选择走一步或者两步，那么到达第m阶的时候，总共有多少种走法？(n0,0m≤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)求解方式上面的方法很容易写出代码求解，但是不同方法的效率相差很大。1.递归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个工人的利益最大化，所以这些顺序就不重要了。•因为这是二维的，最好是列表，那么也自然使用备忘录算法。边界条件便是第一行的数据了。•mNUM(1)时，F(1,m)=0;mNUM(1)时，F(1,m)=AWARD(1)