一、理论：
1、一个模型三个特征：
<1>、“一个模型”：
它指的是动态规划适合解决的问题的模型。一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
<2>、“三个特征”：
-
最优子结构：
最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，可以通过子问题的最优解，推导出问题的最优解。如果把最优子结构对应到动态规划问题模型上，那也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。 -
无后效性：
无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。 -
重复子问题：
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
<3>、“一个模型三个特征”实例剖析：
假设有一个乘以
的矩阵
。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
(1)、是否符合“一个模型”？
从走到
，总共要走
步，也就对应着
个阶段。每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。把状态定义为
，其中i表示行， j表示列。
表达式的值表示从
到达
的最短路径长度。所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。
(2)、是否符合“三个特征”？
刚刚定义状态的时候，把从起始位置到
的最小路径，记作
。因为只能往右或往下移动，所以，只有可能从
或者
两个位置到达
。也就是说，到达
的最短路径要么经过
，要么经过
，而且到达
的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是，
可以通过
和
两个状态推导出来（
）。这就说明，这个问题符合“最优子结构”。
如果走到这个位置，只能通过
，
这两个位置移动过来，也就是说，想要计算
位置对应的状态，只需要关心
，
两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“无后效性”这一特征。
可以用回溯算法来解决这个问题。从左上角到节点对应的位置，有多种路线，说明这个问题中存在“重复子问题”。
二、动态规划解题思路总结：
1、状态转移表法：
首先画出递归树，然后根据递归树画出一个状态表。状态表一般都是二维的，所以可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，将这个递推填表的过程，翻译成代码，就是动态规划代码了。
public int minDistDP(int[][] matrix, int n) {
int[][] states = new int[n][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];
}
2、状态转移方程法：
分析某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。一般情况下，有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。
状态转移方程：
递归加“备忘录”代码：
private int[][] matrix ={{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 = Integer.MAX_VALUE;
if (j-1 >= 0) {
minLeft = minDist(i, j-1);
}
int minUp = Integer.MAX_VALUE;
if (i-1 >= 0) {
minUp = minDist(i-1, j);
}
int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
mem[i][j] = currMinDist;
return currMinDist;
}
