动态规划

概念

任何数学递归公式都可以直接转换成递归算法，但是基本现实是编译器常常不能正确对待递归算法，结果导致低效的程序。当怀疑很可能是这种情况时，我们必须将递归算法写成非递归算法，让后者把那些子问题的答案系统地记录在一个表内。利用这种方法的一种技巧叫做动态规划（dynamic programming）。

斐波那契数

使用如下递归计算斐波那契数是非常低效的，因为子问题被不断重复求解，从而导致指数级的时间复杂度。

由于计算所需要的只是和，因此只需记录最近算出的两个斐波那契数即可，甚至不用记录所有子问题的答案。如下所示的动态规划算法只需O(N)的时间复杂度。

为什么递归求解斐波那契数很低效，因为该算法模拟了递推。为了计算，需要存在一个对和的调用。然而又要递归地对和进行调用，如此就存在两个重复计算的调用。如下图所示，显示了子问题的重复计算。

矩阵乘法的最优顺序安排

问题描述：
将两个阶数分别为pq和qr的矩阵以明显的方式相乘，使用pqr次纯量乘法。计算ABCD需要进行三次矩阵乘法，有多种相乘的顺序，哪种顺序所需的纯量乘法次数最少？其中A的维数为50*10，B的维数为10*40，C的维数为40*30，D的维数为30*5。通过穷举搜索求解的过程如下：
1.A((BC)D)：总计需要16000次乘法；
2.A(B(CD))：总计需要10500次乘法；
3.(AB)(CD)：总计需要36000次乘法；
4.((AB)C)D：总计需要87500次乘法；
5.(A(BC))D：总计需要34500次乘法；
最优的排列顺序2，大约只用了最坏排列顺序4的九分之一的乘法次数，所以确定最优顺序还是值得的。但是通过穷举算法来求解，时间复杂度随矩阵数量N呈指数级增长。下面提供一种优于指数的算法，利用动态规划的思想。

设矩阵为，令是矩阵的列数，则是矩阵的行数（也是矩阵的列数），否则矩阵乘法无法进行。定义为第一个矩阵的行数。

如果我们定义为在最优排序顺序下所需要的乘法次数（为零），则其中三项分别代表计算、以及它们的乘积所需要的乘法次数。这个方程意味着，如果我们有乘法的最优乘法排列顺序，那么子问题和就不能次最优地执行。

这个公式可以直接转换成递归程序，不过，正如上一节所看到的，这样的程序是明显低效的。如果我们用一个表来存放所有子问题的解，可以较高效的实现上述方程。如下是计算示意图，先解决最小的相邻元素的矩阵乘法次数问题（k=1）；接着解决相隔一个元素的矩阵乘法次数问题（k=2），此时需要利用k=1的计算结果；接着解决相隔两个元素的矩阵乘法次数问题（k=3），此时需要利用k=1,2的计算结果。

计算顺序示意图

程序如下所示。除了最后的答案外，我们还要显示实际的乘法顺序，我们通过lastChange矩阵记录分割指标i的值，一旦改变，就记录对应位置i的值。这个程序包含三重for循环，以时间运行。

    private static final Integer INF = Integer.MAX_VALUE;

    /**
     * 计算矩阵乘法的最优顺序: A1*A2*...*AN
     *
     * @param c          长度为N+1, c[0]第1个矩阵的行数, c[1]第1个矩阵的列数,..., c[N]第N个矩阵的列数
     * @param m          维度为(N+1)*(N+1), m[i]m[j]的值为Ai*Ai+1*...*Aj最优顺序所需的乘法次数;
     *                   m[1][N]的值为A1*A2*...*AN最优顺序所需的乘法次数,即所求值;
     * @param lastChange 维度为(N+1)*(N+1), lastChange[i][j]的值为Ai*Ai+1*...*Aj的最优顺序的最后一次划分index,必然为[i,j]中的值
     */
    public static void optMatrix(int[] c, long[][] m, int[][] lastChange) {

        int n = c.length - 1;

        for (int left = 1; left <= n; left++) {
            m[left][left] = 0;
        }

        for (int k = 1; k < n; k++) { // k is right - left
            for (int left = 1; left < n - k; left++) {
                // for each position
                int right = left + k;
                m[left][right] = INF;
                for (int i = left; i < right; i++) {
                    long thisCost = m[left][i] + m[i + 1][right] + c[left - 1] * c[i] * c[right];
                    if (thisCost < m[left][right]) {
                        m[left][right] = thisCost;
                        lastChange[left][right] = i;
                    }
                }
            }
        }

    }

有向图所有点对赋权最短路径

定义为从到，只考虑使用（部分或全部）作为中间顶点的最短路径的权。根据这个定义，是图中从到的最短路径，，其中若不是该图的边则为无穷。

当k>0时，可以给写一个简单公式：

从到只考虑使用作为中间顶点的最短路径，是下面两者的小者：要么是根本不使用作为中间顶点的最短路径；要么是由两条路径->和->合并而成的最短路径，其中每条路径只使用前k-1个顶点作为中间顶点。注意，在以k开始或者结束的路径上以k作为中间顶点对结果没有改进，除非存在一个负的圈，所以有。代码如下。

/**
     * compute all-shortest paths
     * a[][]: 邻接矩阵, 无负圈
     * d[][]: 保存最短路径的值
     * 顶点从0开始编号
     * path[][]: 最短路径可以通过path[][]计算得出
     */
    public static void allPairs(int[][] a, int[][] d, int[][] path) {
        int n = a.length;

        // initialize d and path
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = a[i][j];
                path[i][j] = -1; // not a vertex
            }
        }

        for (int k = 0; k < n; k++) {
            // 考虑使用每个顶点作为中间顶点, k即中间顶点
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (d[i][k] + d[k][j] < d[i][j]) {
                        // update shortest path
                        d[i][j] = d[i][k] + d[k][j];
                        path[i][j] = k;
                    }
                }
            }
        }
    }