从递归转换到动态规划
如果一个递归函数有n个参数，那就定义一个n维数组，数组的下标就是递归函数的取值范围，数组元素的值是递归函数的返回值。
从边界值开始，逐步填充数组，就相当于计算递归函数值的逆过程。
相当于一个从下到上的过程
DP的一般思路
1、把原问题分解成若干个子问题——当子问题全部解决的时候原问题即解决。子问题的解求出之后直接保存——每个子问题只求解一次。
2、确定状态
一个“状态”即为和子问题相关的各个变量的一组取值。一个“状态”对应于一个或者多个子问题，所谓“某个状态”的“值”，就是它所对应的子问题的解。
所有状态的集合，构成问题的“状态空间”——状态空间的大小与时间复杂度直接相关。对于数字三角形，一共有N(N+1)/2个数字，因此状态空间一共有N(N+1)/2个状态。
对于数字三角形：
子问题——第i行j列的数字到底边的最大和
跟子问题相关的变量——i,j
状态——i,j的一组取值，即为状态对应的子问题
状态的值==子问题的解==(i,j)的最大和
有的时候K个整形变量构成一个状态，那么就用K维数组来存储各个状态的值——“值”可以是一个结构体。一个状态的值通常会是一个或者多个子问题的解。
3、确定一个初始状态（边界状态）的值
初始状态可以直接看出——对于数字三角形，初始状态就是底边数字，值即为底边数字的值
4、确定状态转移方程
找出不同状态之间如何转移——从一个已知状态到一个未知状态。即从一个或者多个“值”已知的状态，求出另一个未知状态的值——这个步骤可以用递推公式表示，即为状态转移方程
什么时候使用DP
1、问题具有最优子结构的性质——即问题的最优解所包含的子问题的解也是
最优的
2、无后效性——当前若干个状态的值不受路径影响，只跟状态有关
网友评论