动态规划初步
动态规划初步
开始之前
首先我们考虑一下以下的问题：
- 什么是动态规划，动态规划与递推有什么关系
- 动态规划的关键点是什么
- 动态规划怎么保证每处的值都是最优
- 动态规划有哪几种解题模板
- 动态规划有哪些应用
正文
带着这些问题，就要更深的了解动态规划了。
首先回到第一个问题：
什么是动态规划，动态规划与递推有什么关系
我个人的理解是通过寻求问题的子问题来递推解决问题的一种方法。
而递推是动态规划中要用到的一部分，而且并不只是简单的递推，而是要根据情况进行判断选出最优的结果进行递推，例如：
d(i, j) = max(d(i + 1, j), d(i + 1, j + 1)) + a(i, j)
而递推则往往是简单的相邻几项的关系，例如：
d(i) = 3d(i - 1) + 2
既然递推不是动态规划的关键，那动态规划的关键点是什么呢？
这样就来到了第二个问题：
动态规划的关键点是什么
状态
- 简单来说就是整个过程中的某个点，以及一些属性
指标函数&决策&状态转移方程
- 指标函数是一个最优的函数，它的一个特定的值往往就是问题的解答，例如
上面的d(i, j)是从(i, j)出发的最大值，那么一个特定的值(1, 1)就是从这个点到最底层的最大的路径长度
而指标函数的选取是动态规划的一个关键，选一个好的指标函数能大大的让问题简化
另外对于同一个状态的选取，指标函数通常有两种互相对称的写法，比如和上面的对称的是：到(i, j)的最大值
决策是状态转移的方向，通常两个这个状态到下一个状态总是有多种方向可以选择，而我们要选择的总是最佳决策
状态转移方程则是用指标函数来表示不同状态的转移过程，选出最优决策，表示状态间的数学关系
虽然动态规划是一层层推下来的，那如果到了后面的情况发现前面某一步的另一种决策有更优的结果是怎么处理的呢？怎么保证最后的结果总是最优？
动态规划怎么保证每处的值都是最优
这是由一个叫“最优子结构”的部分保证的，看维基百科上我们可以知道：
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。
也就是说因为每一步都是由一个特定的值和最优值组成的，每一步最优值则保证了下一步甚至到结果都是最优值。
当然如果状态和指标函数选取的不好，那么可能就陷入一个“不能保证最优子结构”的情况了，比如杭电上的龟兔赛跑问题，如果选取(i, j)作为状态，i为当前充电站的编号，j为当前还可以跑的里程。因为下一步的里程还是和这一步相关，所以保证了前面的最优并不能保证接下来的都是最优的，这部分就要思考清楚了(这也是最难的部分)。
动态规划有哪几种解题模板
下面以数字三角形为例
- 递推法
int i, j; // 总是要把最开始的状态先初始化，这里是最下面一层的状态 for (int i = 1; i <= n; ++i) d[n][i] = a[n][j]; // 由于这个图形是二元的，于是有二重循环 for (int i = n - 1; i >= 1; --i) for (int j = 1; j <= i; ++j) d[i][j] = a[i][j] + max(d[i + 1][j], d[i + 1][j + 1]);
经过循环进行递推，最后的结果储存在数组d中
- 记忆化搜索
在递归的基础上对已经访问的数据进行标记，避免了重叠子问题的多次求解
// 初始化，方便之后的判断
memset(d, -1, sizeof(d));
int solve(int i, int j)
{
if (d[i][j] >= 0) return d[i][j];
// 返回的时候顺便进行了“记忆”
return d[i][j] = a[i][j] + (i == n? 0: max(solve(i + 1,j), solve(i + 1, j + 1);
}基本的思想主要就是两种，而解题的关键则是确定状态以及指标函数了
动态规划有哪些应用
下面就分析一下讲过和做过的题目：
数字三角形
- 状态：(i, j)，位置
- 指标函数d(i, j)，从(i, j)出发的最大长度
- 决策：向下走的方向
- 状态转移方程
d[i][j] = a[i][j] + max(d[i + 1][j], d[i + 1][j + 1]);
嵌套矩形（有向无环图不固定起点终点的最大路径）
- 状态：i，结点
- 指标函数d(i)，从i出发的最大长度
- 决策：到下一个结点选择的边
- 状态转移方程
d[i] = max{d[j]}; // j为和i相邻的结点
硬币问题（有向无环图固定起点终点的最大/小路径）
- 状态：i，结点
- 指标函数d(i)，从i出发的最大/小长度
- 决策：到下一个结点选择的硬币的种类（硬币面值要比剩下的钱要小）
- 状态转移方程
d[i] = max(d[i], d[i - v[t]] + 1); // t是要从大到小（最小数量）进行循环 // 因此要求出所有的长度也必然要对i进行循环，也就是两层循环
多段图最短路径（多段决策）
- 状态：(i, j)，行，列
- 指标函数d(i, j)，从(i, j)出发到最后一列的最大长度
- 阶段：列
- 决策：到下一列走的方向
- 状态转移方程
d[i][j] = max(d[i + n][j + 1] + a[i][j]); // n是三种决策的一个表示，通过循环来判断 // 如果要按照字典序输出，则最好按照行数的大小进行排序
注意：
这个模型到完成的时候的步数已经确定了，所以可以根据每一步来当做阶段，阶段可以作为状态的一部分来简化模型
0-1背包（多段决策）
- 状态：(i, j)，当前层，背包剩余容量
- 指标函数d(i, j)，从(i, j)出发到最后一列的最大长度
- 阶段：物品，因为每个物品都只有一个，也是“过了就没有了”，于是也可以用阶段表示
- 决策：是否把物品放入背包
- 状态转移方程
// 这里j保证了不会有一开始选很大后面没位置选的情况，因为j会从0到最大容量进行循环 // 前面的情况如果不是最优就会被排除 // 也是对i对j两层循环 d[i][j] = max(d[i + 1][j], d[i + 1][j - V[i]]);
龟兔赛跑
- 状态：i，充电站
- 指标函数d(i, j)，从i到j的过程中充一次电并且时间最短，T(i)到达i最小时间
- 决策：是否充电
- 状态转移方程
// 也是对i对j两层循环 d[i] = min(T(i) + d(i, j), T(j));
最长上升子序列(LIS)
- 状态：i，序列长
- 指标函数d(i)，长度为i序列的最长长度
- 决策：新增加的数是否比原来最大的大
- 状态转移方程
// 也是对i对j两层循环 d[i] = max(0, d(j) | j < i, A[j] < A[i]);
最长公共子序列(LCS)
- 状态：(i, j)，A，B序列长
- 指标函数d(i, j)，公共子序列最大长度
- 决策：两个序列是否正好是最后一位相同
- 状态转移方程
// i从0～m循环，j从0～n循环 A[i] == B[j] d(i, j) = d(i - 1, j - 1) + 1; else d(i, j) = max(d(i - 1, j), d(i, j - 1));
最后
动态转移方程的循环往往不止一层，这个地方一定要想清楚。
看了这么多，还是不会做题怎么办？
我也在苦恼这事呢（哭。