递归到动规的一般转化方法
递归函数有n个参数,就定义一个n维的数组,数组的下标是递归函数参数的取值范围,数组元素的值是递归函数的返回值,这样就可以从边界值开始,逐步填充数组,相当于计算递归函数值的逆过程。
动规解题的一般思路
能用动规解决的问题的特点
1) 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质。
2) 无后效性。当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。