前言
上一节通过两个经理案例初步认识动态规划，今天这一节主要讲动态规划的理论知识。
“一个模型三个特征”理论讲解
实际上，动态规划作为一个非常成熟的算法思想，这部分理论总结为“一个模型三个特征”。
一个模型
一个模型指动态规划适合解决的问题模型。这个模型定义为“多阶段决策最优解模型”。
一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的值。
三个特征
三个特征分别是：最优子结构、无后效性和重复子问题。
- 最优子结构：问题的最优解包含子问题的最优解。
- 无后效性：有两层含义。
- 第一层，在推导后面阶段的状态时，只关心前面阶段的状态值。
- 第二层，某阶段的状态一旦确定，就不受之后阶段的决策影响。
- 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
两种动态规划解题思路总结
解决动态规划问题，一般有两种思路。分别是状态转移表法和状态转移方程法。
状态转移表法
状态转移表法的解题思路概括为：回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。
我们来看一下，如何套用状态转移表法来解决动态规划问题。
假设我们有一个n乘以n的矩阵w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。那从左上角移动到右下角的最短路径长度是多少？
回溯算法实现
public class Solution {
private int minDist = int.MaxValue;
public int MinDist { get { return minDist; } }
// 调用方式：MinDistBT(0, 0, 0, w, n);
public void MinDistBT (int i, int j, int dist, int[][] w, int n) {
// 到达n-1, n-1这个位置了
if (i == n - 1 && j == n - 1) {
dist = dist + w[i][j];
if (dist < minDist) minDist = dist;
return;
}
if (i < n - 1) { // 往下走，更新i=i+1, j=j
MinDistBT (i + 1, j, dist + w[i][j], w, n);
}
if (j < n - 1) { // 往右走，更新i=i, j=j+1
MinDistBT (i, j + 1, dist + w[i][j], w, n);
}
}
}
定义状态
从回溯代码的函数调用可知，每一个状态包含三个变量(i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达(i, j)的路径长度。
画递归树
有了回溯代码和状态定义，把每个状态作为一个节点，画出递归树。
找重复子问题
从上图可知，存在重复子问题。
画状态转移表
我们画出一个二维状态表，表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。
根据递推关系填表
按照决策过程，通过不断状态递推演进，将状态表填好。
将填表过程翻译成代码
public class Solution2 {
public int MinDistDP (int[][] matrix, int n) {
int[][] states = new int[n][];
for (int i = 0; i < n; i++) {
states[i] = new int[n];
}
int sum = 0;
for (int j = 0; j < n; ++j) { // 初始化states的第一行数据
sum += matrix[0][j];
states[0][j] = sum;
}
sum = 0;
for (int i = 0; i < n; ++i) { // 初始化states的第一列数据
sum += matrix[i][0];
states[i][0] = sum;
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < n; ++j) {
states[i][j] = matrix[i][j] + Math.Min (states[i][j - 1], states[i - 1][j]);
}
}
return states[n - 1][n - 1];
}
}
状态转移方程法
状态转移方程法的解题思路概括为：找最优子结构-写状态转移方程-将状态转移方程翻译成代码。
还是拿上面的例子来说明。
找最优子结构
min_dist(i, j)可以通过min_dist(i, j-1)和min_dist(i-1, j)两个状态推导出来，符合“最优子结构”。
写状态转移方程
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
强调一下，状态转移方程是解决动态规划的关键。
将状态转移方程翻译成代码
一般情况下，有两种代码实现方法：
- 递归+“备忘录”
- 迭代递推
用递归+“备忘录”将状态转移方程翻译成代码。
public class Solution3 {
private int[, ] matrix = new int[4, 4] { { 1, 3, 5, 9 }, { 2, 1, 3, 4 }, { 5, 2, 6, 7 }, { 6, 8, 4, 3 } };
private int n = 4;
private int[, ] mem = new int[4, 4];
public int MinDist (int i, int j) { // 调用MinDist(n-1, n-1)
if (i == 0 && j == 0) return matrix[0, 0];
if (mem[i, j] > 0) return mem[i, j];
int minLeft = int.MaxValue;
if (j - 1 >= 0) {
minLeft = MinDist (i, j - 1);
}
int minUp = int.MaxValue;
if (i - 1 >= 0) {
minUp = MinDist (i - 1, j);
}
int curMinDist = matrix[i, j] + Math.Min (minLeft, minUp);
mem[i, j] = curMinDist;
return curMinDist;
}
}
总结
动态规划有两种解题思路：状态转移表法和状态转移方程法。
状态转移表法的解题思路概括为：回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。
状态转移方程法的解题思路概括为：找最优子结构-写状态转移方程-将状态转移方程翻译成代码。