递归到动规的一般转化方法
递归函数有n个参数, 就定义一个n维数组:
- 数组下标: 递归函数参数的取值范围;
- 数组元素的值: 递归函数的返回值.
这样就可以从边界值开始, 逐步填充数组, 相当于计算递归函数值
的逆过程.
将原问题分解为子问题
把原问题分解为若干个子问题, 子问题和原问题形式相同或类似, 只不过规模变小了. 子问题都解决, 原问题即解决(数字三角形为例)
子问题的解一旦求出就被保存, 所以每个子问题只需求解一次.
确定状态
动态规划解题时, 我们往往将和子问题相关的各个变量的一组取值, 称之为一个状态. 一个状态对应一个或多个子问题, 所谓某个状态下的值, 就是这个状态所对应子问题的解.
所有状态的集合, 构成问题的状态空间. 其大小, 与动态规划解决问题的时间复杂度直接相关. 以数字三角形为例, 一个有 N × (N+1) / 2 个数字, 所以这个问题的状态空间里就一 共有 N × (N+1) / 2 个状态.
整个问题的时间复杂度就状态数目乘以计算每个状态所需时间.
再数字三角形里每个状态只需经过一次, 且再每个状态上作计算所花费的时间都是和N无关的常数.
用动态规划解题, 经常碰到的情况是, K个整型变量能构成一个状态(如数字三角形中的行号和列号这两个变量所构成的状态).
如果这K个整型变量的取值范围分别是N, N, …, N, 那么我们就可以用一个K维数组array[N1][N2]…[Nk]来存储各个状态的值.这个值未必就是一个整数或浮点数, 可能是一个结构体.
一个状态下的值通常是一个或多个子问题的解.
确定一些初始状态(边界状态)的值
以数字三角形为例, 初始状态就是底边数字, 值就是底边数字值.
确定状态转移方程
定义出什么是状态, 以及在该状态下的值后, 就要找出不同的状态之间如何迁移—即如何从一个或多个值已知的状态, 求出另一个状态的值(人人为我递推型).
状态的迁移可以用递推公式表示, 此公式被称为状态转移方程:
以数字三角形的状态转移方程为例:
能用动规解决的问题的特点
问题具有最优子结构性质
若问题最优解所包含的子问题的解也是最优的, 我们就乘该问题具有最优子结构性质.
无后效性
当前的若干个状态值一旦确定, 则此后过程的演变就只和这若干个状态的值有关, 和之前是采取哪种手段或经过哪路径演变到当前的这若干个状态, 没有关系.
动态规划的算法设计
从编译原理的角度来看，动态规划的算法设计有2个思路：
Top-Down Approach：类似于上下文无关文法的派生，它是从树顶一直递归下降的。我们要求某个值，便从相应的递归关系一直递归到边界。由于中途可能会存在重复运算，所以会额外维护一个备忘录（由此又称该方法为记忆化搜索）。备忘录不断保存中间结果，在某个递归函数需要时取出相应的结果。
Bottom-Up Approach：类似于上下文无关文法的归约，它从叶子节点一直归约到树根。即从边界条件开始，一直递推到我们需要的位置。
在分析问题时，一般采用递归思维，但在编码上，一般使用递推方式。
若有收获，就点个赞吧
0 人点赞
