Title:算法设计与分析学习笔记（二）：动态规划（1）
Date:2014-12-11 21:50
Catagory:算法学习
动态规划
Slug:dynamic_programming

动态规划的思想

动态规划与分治法类似，也是将问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。分治法在问题较大且相互不独立的情况下，由于分解得到的子问题数目太多，各个递归子问题被重复计算多次，求解过程呈幂级数增长，其时间复杂度为n的指数时间。与分治法不同，动态规划方法采用自底向上的递推方式求解，并且经分解得到的子问题往往不是相互独立的，根据子问题的相关性，在每步列出可能的局部解中选出能产生最佳解的部分，并将计算过程填表，只要某个子问题被解决,将不会被多次计算，从而减少了算法的时间复杂度。

求解问题时每次决策依赖于当前状态，又随即引起状态的转移，决策序列在变化的状态中逐步产生，这种用多阶段最优化决策方式解决问题的过程称为动态规划。

递推关系(状态转移方程)是实现由分解后的子问题向最终问题求解转化的纽带。
填表技术是把计算过的所有子问题的解都记录下来，由于将原问题分解后的各个子问题可能存在重复性，所以当以后重复遇到该子问题时，只需要查表继续问题的求解，而不需要重复计算，这样就节省了很多计算时间，这就是动态规划的精髓。

动态规划建立在最优原则的基础上，在每一步决策上列出各种可能的局部解，按某些条件舍弃肯定不能得到最优解的局部解，通过逐步筛选，减少计算量。依据最优性原理，寻找最优判断序列，不论初始状态如何，下一次决策必须相对前一次决策产生的新状态构成最优序列。每一步都经过筛选，以每一步的最优性来保证全局的最优性。

动态规划的基本要素

1.最优子结构

当前问题的最优解包含了其子问题的最优解时，称为具有最优子结构。

动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。要做到这一点，就必须将原问题分解为几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类的子问题，然后逐个求解。即从边界条件开始，逐阶段递推寻优，在每一个子问题的求解中，均利用它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解就是整个问题的最优解，这样就说明具有最优子结构。

2.子问题重叠性

在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，保存起来，查找的时候只是用常数时间，所以通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。