一、一个模型三个特征理论

一个模型：动态规划适合解决的问题的模型。把这个模型定义为”多阶段决策最优解模型“，解决的问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

三个特征：最优子结构、无后效性和重复子问题。

1. 最优子结构

最优子结构指的是，问题最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

2. 无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响，无后效性是一个非常 “宽松” 的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

3. 重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

"一个模型三个特征"实例解析

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

我们先看看，这个问题是否符合 “一个模型”？

从（0,0) 走到（n-1, n-1)，总共要走2*(n-1)步，也就对应着2*(n-1)个阶段。每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。

我们把状态定义为min_dis(i, j)，其中 i 表示行，j 表示列。min_dist表达式的值表示从(0, 0)到达(i, j)的最短长度。所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。

我们再来看，这个问题是否符合 “三个特征”?

从左上角到节点对应的位置，有多种路线，存在着重复子问题。

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

我们把从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min_dist(i, j)。因为我们只能往右或往下移动，所以只有可能从 (i-1, j)，(i, j-1) 两个位置到达 (i, j) 。也就是说，到达 (i, j) 的最短路径要么经过 (i-1, j)，要么经过 (i, j-1) ，而且到达 (i, j) 的最短路径肯定包含这两个位置的最短路径之一。换句话就是，min_dist(i, j) 可以 min_dist(i-1, j) 和 min_dist(i, j-1) 这两个状态推导出来。这就说明，这个问题符合 ”最优子结构“ 。

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

二、动态规划两种解题思路

1. 状态转移表法

先用回溯算法看是否能找到重复子问题，找到后，有两种处理思路，第一种直接用回溯加 ”备忘录“ 的方法来避免重复子问题。从执行效率上来讲，这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法，状态转移表法。

我们先画出一个状态表。状态表一般都是二维的。所以可以把它想成二维数组。其中，每个状态包含三个变量，行、列、数组值。根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，将这个递推填表的过程，翻遍成代码，就是动态规则的代码了；

如果问题的状态比较复杂，需要很多变量来表示，对应的状态表可能就是高维的，比如三维、四维。那就不适合用状态转移表来解决了。一方面因为高维状态转移表不好画图表示，另一方面是因为人脑确实不擅长思考高维的东西。

回溯算法的代码如下：

  // 记录最短路径
    int minDist = Integer.MAX_VALUE;

    /**
     * 回溯算法—— 计算计算最短路径
     *
     * @param i    行位置
     * @param j    列位置
     * @param w    矩阵
     * @param n    矩阵长度
     * @param dist 累计路径长度
     */
    public void minDistBT(int i, int j, int[][] w, int n, int dist) {

        dist += w[i][j];

        // 到达尽头
        if (i == n - 1 && j == n - 1) {
            // 是否最短路径
            if (dist < minDist) minDist = dist;
            return;
        }


        // 往下走
        if (i < n - 1) {
            minDistBT(i + 1, j, w, n, dist);
        }

        // 往右走
        if (j < n - 1) {
            minDistBT(i, j + 1, w, n, dist);
        }
    }

有回溯代码之后，画出递归树，以此来寻找重复子问题。在递归树中，一个状态（也就是一个节点）包含三个变量 (i, i, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的路径长度。从图中，我们看出，尽管 (i, i, dist) 不存在重复的，但是 (i, j) 重复的有很多，对于 (i, j) 重复的节点，只需要选择 dist 最小的节点，继续递归求解，其它节点就可以舍弃了。

既然存在重复子问题，我们就可以尝试看下，是否可以用动态规划来解决呢？

画出二维状态表，表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。按照决策过程，通过不断状态递推演进，将状态表填好。为了方便代码实现，我们按行进行依次填充。

填表完成了，代码实现就简单多了。实现如下：

 /**
     * 动态规划 —— 计算计算最短路径
     *
     * @param w 矩阵
     * @param n 矩阵长度
     * @return 起点到终点的最短距离
     */
    public int minDistDP(int[][] w, int n) {
        // 新建状态转移表
        int[][] states = new int[n][n];
        // 初始化 0 行， 0 列
        int col = 0, row = 0;
        for (int i = 0; i < n; i++) {
            row += w[0][i];
            states[0][i] = row;
            col += w[i][0];
            states[i][0] = col;
        }
        // 补充转移表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                states[i][j] = w[i][j] + Math.min(states[i - 1][j], states[i][j - 1]);
            }
        }
        return states[n - 1][n - 1];
    }

状态转移表法可以概括为：回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码

2. 状态转移方程法

状态转移方程法有点类似递归的解题思路，需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也是状态转移方程。一般情况下，有两种代码实现方法一种是递归加 ”备忘录“，另一种是迭代递推。

min_dist(i, j) = w[i][j] + Math.min(min_dist(i, j-1),min_dist(i-1, j))

递归加 ”备忘录“的方式，将状态转移方程翻译成代码实现如下：

    private int[][] w = new int[][]{{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
    private int n = 4;
    // 备忘录
    private int[][] men = new int[n][n];
 /**
     * 递归加备忘录 —— 计算最短路径 调用 minDistR(n-1, n-1)
     *
     * @param i 行下标
     * @param j 列下标
     * @return 起点到终点的最短距离
     */
    public int minDistR(int i, int j) {
        if (i == 0 && j == 0) {
            return matrix[0][0];
        }
        // 备忘录已经存在，不用递归了
        if (men[i][j] > 0) {
            return men[i][j];
        }
        int minleft = Integer.MAX_VALUE;
        if (j - 1 >= 0) {
            minleft = minDistR(i, j - 1);
        }
        int minTop = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            minTop = minDistR(i - 1, j);
        }
        int currMinDist = matrix[i][j] + Math.min(minTop, minleft);
        men[i][j] = currMinDist;
        return currMinDist;
    }

状态转移方程法的可以概括为：找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码

三、四种算法思想比较分析

贪心、回溯、动态规划可以归为一类，分治单独作为一类，为什么呢？前三个算法解决问题的模型都可以抽象成”多阶段决策最优解模型“，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多”阶段决策最优模型“。

回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，它的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题，对于大规模数据的问题，用回溯算法解决的执行效率就很低。基本能用动态规划、贪心解决的问题，都可以回溯算法解决。

动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性。

其中，最优子结构、无后效性跟动态规划中的一样。”贪心选择性“是，通过局部最优的选择，能产生全局的最优选择，第一个阶段，者选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。