动态规划一般可分为四类:
- 线性动规: 最长上升子序列,拦截导弹等
- 区间动规: 石子合并,矩阵乘法等
- 树形动规: 最优二叉查找树等
- 背包问题: 01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶
动态规划步骤可以分为:
- 描述最优解的结构
- 递归定义子问题最优解
- 自底向上计算每个子问题的最优解
- 通过计算结果得到最优解
需要注意的是计算过程是自底向上的,这是由于动态规划的要素之一重叠子问题存在.自底向上构造意味着通过一个备忘录的结构可以记录子问题的解,不需要重复计算,
动态规划的另外一个要素是最优子结构,有这一特征,就可以考虑动态规划(当然也可能使用贪心算法).
动态规划解题的关键是,建立状态转移方程 : f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]},其中opt是最优解选择依据,U是状态,X是策略, L[Uk-1,Xk-1]是状态Uk-1通过策略Xk-1到达状态Uk的费用,初始 f[U1],通过状态转移方程自底向上计算状态转移矩阵后可以得到结果: f[Un]
下面会介绍动态规划的一些经典问题,篇幅所限,会分成多个页面介绍:
与分治法类似,动态规划也是将问题分解成结构一样的子问题,然后通过解决子问题,得到问题的最解,但是不同的是,分治法子问题之间互相独立,每个问题计算后合并得到最终问题,但是动态规划子问题之间是有关系的,因此设计自底向上的方法,记录子问题解,上层问题计算时,可能会使用到这些子问题的解.