快速学习算法：[1]动态规划

电脑

python环境

发现问题：举个简单递归例子，著名的斐波那契数列，1、1、2、3、 5、 8...，我们可以使用递归的方法解决任意序号为n的斐波那契数，根据其递归式，如图，小编在写出如下代码，并经过测试发现是正确的

但是从递归树中，不难发现许多计算规模相同的子问题被重复计算，如图所示，为计算fib(5)，由于递归调用，需要调用fib(4)和fib(3)，fib(4)递归调用fib(3)和fib(2)，相同的子问题fib(3)被重复计算，对时间和空间造成了浪费

仔细观察我们发现，这个问题有一下几个特点：1、该问题包含一个最优子结构；何为最优子结构？即一个问题的最优解包含其子问题的最优解，就称此问题具有最优子结构性质。在斐波那契数列问题中，不难发现其最优子结构表现在其递归式，即 当n>1时，f(n)=f(n-1)+f(n-2)

2、该问题是有不断求解重叠子问题而解出的；例如，求解fib(5)时，我们两次求解相同的问题fib(3)，fib(3)是fib(5)的重叠子问题

3、重构子问题解得到最终解；在本题中，此特点即是递归的返回调用特点

综上，对于重复的解，不妨设计一个数组储存这些解的结果，将时间复杂性转换为空间复杂性，如图，小编修改了代码

接下来我们测试一下，效果非常明显，这也是小编选择python环境的原因啦，如图，我们使用修改后的fib2计算fib2(100000)，小编秒得答案；而使用先前的递归方案计算fib(100000)，不仅没有计算出，反而报错(python递归层有限制)注：小编是 i7的本本，ubuntu14.04环境下测试的

至此，小编总结一下应用动态规划的方法：1、刻画一个最优解的结构特征；2、递归地定义最优解的解；3、计算最优解的解，通常采用自底向上的方法，即任何子问题的求解依赖于更小的子问题的求解，当按照顺序求解子问题时，它所依赖的那些子问题已经全部解决；4、利用计算出的信息构造一个最优解～～