【dp笔记】动态规划解题一般思路

课程笔记：程序设计与算法（二）算法基础：dp

递归到动规的一般转化方法

• 递归函数有n个参数就定义n维的数组
• 数组的下标是递归函数参数的取值范围
• 数组元素的值是递归函数的返回值
• 从边界值开始逐步填充数组（计算递归函数值的逆过程）

动态规划接替的一般思路

1. 将元问题分解为子问题
   • 把元问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决了，原问题即解决（数字三角形例）。
   • 子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。
2. 确定状态
   • 状态：和子问题相关的各个变量的一组取值 ，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某“状态的值”，就是这个“状态”所对应的子问题的解。
   • 状态空间：所有“状态”的集合，构成问题的“状态空间”，“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。（在数字三角形的例子中，状态空间一共有N X (N+1)/2个状态）
     整个问题的时间复杂度是状态数目诚意每个状态所需时间
     常常碰到的情况是，K个整型变量能构成一个状态（数字三角形的行列两个整型）。如果这K个的整型变量的取值范围分别是N1，N2，....Nk，那么就可以用K维数组array[N1][N2]....[Nk]来存储各个状态的“值”。这个“值”未必就是一个整型或是浮点数，可能需要一个结构才能表示，那么array就可以是一个结构数组。一个“状态”下的“值”通常会是一个或多个子问题的解。
3. 确定一些初始状态（边界状态）的值
4. 确定状态转移方程
   • 定义出什么是”状态“，以及在该”状态“下的”值“后，就要找出不同的状态之间如何迁移——即如何从一个或多个“值”已知的“状态”，求出另一个“状态”的值（“人人为我”递推型）。
   • 状态的迁移可以用递推公式表示，此地推公式也可以被称作“状态转移方程”。
     数字三角形的状态转移方程：
     

能用动规解决的问题的特点

1. 问题具有最优子结构性质。
   如果问题的最优解包含的子问题的解也是最优的，我们就称该问题具有最优子结构

2. 无后效性
   当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这个若干个状态，没有关系。

例题

最长上升子序列