动态规划之状态转移方程-NOIP提高组历年高频考点(4)
通过分析NOIP2011-2018年提高组的试题我们就会发现，考察最多的考点前三名就是模拟，动态规划和贪心算法。今天我们来介绍一下动态规划常用的状态转移方程。
设计一个动态规划算法，有以下四个步骤：
1、刻画一个最优解的结构特征。
2、递归地定义最优解的值。
3、计算最优解的值，通常采用自底向上的方法。
4、利用计算出的信息构造一个最优解。
对于确定状态转移方程就在第一步和第二步中，首先要确定问题的决策对象，接着对决策对象划分阶段并确定各个阶段的状态变量，最后建立各阶段的状态变量的转移方程。
动态规划算法三要素（摘自黑书，总结的很好，很有概括性）：
①所有不同的子问题组成的表
②解决问题的依赖关系可以看成是一个图
③填充子问题的顺序（即对②的图进行拓扑排序，填充的过程称为状态转移）；
则如果子问题的数目为O(nt)，每个子问题需要用到O(ne)个子问题的结果，那么我们称它为
tD/eD的问题，于是可以总结出四类常用的动态规划方程：
（下面会把opt作为取最优值的函数（一般取min或max）, w(j, i)为一个实函数，其它变量都可以在常数时间计算出来）。)
1、1D/1D
d[i] = opt{ d[j] + w(j, i) | 0 <= i < j } (1 <= i <= n)
2、2D/0D
d[i][j] = opt{ d[i-1][j] + xi, d[i][j-1] + yj, d[i-1][j-1] + zij } (1<= i, j <= n)
最典型的见最长公共子序列问题。
3、2D/1D
d[i][j] = w(i, j) + opt{ d[i][k-1] + d[k][j] }, (1 <= i < j <= n)
区间模型常用方程。
另外一种常用的2D/1D的方程为：
d[i][j] = opt{ d[i-1][k] + w(i, j, k) | k < j } (1<= i <= n, 1 <= j <= m)
4、2D/2D
d[i][j] = opt{ d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j}
常见于二维的迷宫问题，由于复杂度比较大，所以一般配合数据结构优化，如线段树、树状数组等。
对于一个tD/eD 的动态规划问题，在不经过任何优化的情况下，可以粗略得到一个时间复杂度是
O(nt+e)，空间复杂度是O(nt)的算法，大多数情况下空间复杂度是很容易优化的，难点在于时间复杂度。