一、理论：

1、一个模型三个特征：

<1>、“一个模型”：

它指的是动态规划适合解决的问题的模型。一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

<2>、“三个特征”：

最优子结构：
最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，可以通过子问题的最优解，推导出问题的最优解。如果把最优子结构对应到动态规划问题模型上，那也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
无后效性：
无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
重复子问题：
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

<3>、“一个模型三个特征”实例剖析：

假设有一个 $n$ 乘以 $n$ 的矩阵 $w[n][n]$ 。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？

(1)、是否符合“一个模型”？

从 $(0, 0)$ 走到 $(n-1, n-1)$ ，总共要走 $2*(n-1)$ 步，也就对应着 $2*(n-1)$ 个阶段。每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。把状态定义为 $min\_dist(i, j)$ ，其中i表示行， j表示列。 $min\_dist$ 表达式的值表示从 $(0, 0)$ 到达 $(i, j)$ 的最短路径长度。所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。

(2)、是否符合“三个特征”？

刚刚定义状态的时候，把从起始位置 $(0, 0)$ 到 $(i, j)$ 的最小路径，记作 $min\_dist(i, j)$ 。因为只能往右或往下移动，所以，只有可能从 $(i, j-1)$ 或者 $(i-1, j)$ 两个位置到达 $(i, j)$ 。也就是说，到达 $(i, j)$ 的最短路径要么经过 $(i, j-1)$ ，要么经过 $(i-1, j)$ ，而且到达 $(i, j)$ 的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是， $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))$ ）。这就说明，这个问题符合“最优子结构”。

如果走到 $(i, j)$ 这个位置，只能通过 $(i-1, j)$ ， $(i, j-1)$ 这两个位置移动过来，也就是说，想要计算 $(i, j)$ 位置对应的状态，只需要关心 $(i-1, j)$ ， $(i, j-1)$ 两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“无后效性”这一特征。

可以用回溯算法来解决这个问题。从左上角到节点对应的位置，有多种路线，说明这个问题中存在“重复子问题”。

二、动态规划解题思路总结：

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、状态转移方程法：

分析某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。一般情况下，有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。
状态转移方程： $min\_dist(i, j) = w[i][j] + min(min\_dist(i, j-1), min\_dist(i-1, j))$

递归加“备忘录”代码：
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;
}

数据结构与算法Day34----动态规划(二)