动态规划矩阵连乘

Throw the problem

事情是这样的，有这样一群捣鼓矩阵的人，他们模拟数的运算法则，整出了矩阵的运算法则。他们发现矩阵A和矩阵B相乘得到矩阵C要做很多次乘法。两个矩阵相乘，计算这个有手就行。三个矩阵相乘还可以接受，四个的话就有点慌，五个的话就有点吃力，六个、七个…既然人算费力，那就交给鸡算，呸，机算。虽然说不用人算，但是矩阵链的长度一上来，电脑也顶不住啊。这帮人开始思考能不能尽可能用最少的乘法次数来实现矩阵的连乘，他们联想到数的运算法则的乘法结合律,因为相邻的矩阵之间是可以若干个组合的。如果给他们加上括号以此来决定乘法的优先级，岂不美哉？光想没用，那就是试试呗。这一试就试出“问题”了。他们发现通过这种“结合运算”的方式，都能得到最终的结果，但是中间用到的乘法次数多少却是“两极分化”!

举个栗子：比如 A1 = 10x100，A2 = 100x5，A3 = 5x50，假如矩阵组合的方式为 ((A1A2)A3) 那么总的相乘次数应为 101005+10550 = 7500，而假如矩阵的组合方式为 (A1(A2A3)) 那么相乘的次数应为 100550+1010050 = 75000，我们可以发现两种不同的组合方式的相乘次数竟然相差这么多。

因此，如何找到最少的相乘次数显得尤为重要，那么该如何解决这个问题呢？

How 2 solve this shit？

Recursion

对于一个规模比较庞大的问题，我们首先想到的就是嫩不能把问题分解成若干个子问题。对于矩阵链（MatrixChain），我们可以递归一下

图中用红色方框框起来的代表在递归的过程中，会被重复计算的矩阵链，这还只是四个矩阵，那如果是四十个，四百个…重复计算的矩阵链只会越来越多（这谁顶得住啊.jpg），因此我们希望寻找更好的方法来解决它。

Dynamic planning

要解决重复计算的问题，我们能想到的是用一张表来保存每次计算出的矩阵连乘积，如果在后续的计算中要用到原先的结果，只需要去表中查找就好了。于是乎，动态规划就起了作用。那么，啥是动态规划？

What is it?

先来看它的官方定义：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

PS：其实在生活中，我们有时候也会使用动态规划这一思想。比如，公司评选优秀员工（最），直接评选不好安排，但是我们可以“自底向上”地比较筛选，那方法就是：选出每个小组表现优秀的员工，又因为一个部门有很多小组，这样能选出一个部门的优秀员工，最后公司又是由很多部门组成的，最后通过类似“集成”的形式就能选出最优秀的员工了。

Exert it！

那么，对于矩阵链连乘积次数的求法，也能用类似的思路（自底向上），因为一个矩阵相乘的需要的连乘积次数为0。

所以我们先算出两个两个矩阵相乘的连乘积，然后把结果分别存入一张记录表里
接着计算三个矩阵链的…
四个的
五个的
…………….

最后我们需要几个变量

p 数组用于存放每个矩阵的维数（每个矩阵对应的行和列）
m 一个二维数组，用于存放计算某一个矩阵链所需的【连乘积】的次数
s 还是一个二维数组，用于存放矩阵链Ai···Aj的断裂点（k的位置）

拿两个矩阵相乘的情况举例，起始矩阵下标i从1开始，而i最后的位置应该为n-2，因为我们当前为两个矩阵相乘，到最后时结尾矩阵下标j位于整个矩阵序列的结尾处，所以此时起始矩阵下标i应该在结尾矩阵的下标j往回减2。结尾坐标的起始位置就是起始坐标的下标加上当前相乘矩阵的数目。举个例子，比如当前为两个矩阵相乘，那么 r = 2，那么起始坐标 i 的开始位置就是 0，结束位置就为 n - r，结尾下标为 j = i + n - 1。

然后我们在这个区间内再来求取断点 k ，断点的取值范围应该为[i,j)，然后对区间内的所有情况进行计算，即 m[i][k] + m[k+1][j] + 结果矩阵相乘次数（这里需要注意一下，这里是为了好理解，其实按照我们给定的输入，它的每三个数字代表两个矩阵，即比如 {35，30，25}，对应的矩阵应为 A1 = 35x30，A2 = 30x25。所以完全写成递归式应该为 m[i][k] + m[k+1][j] + p[i]p[k+1]*p[j]），比如当 i = i，r = 2 时，j = 1，k = i = 1 那么这时当前断点开始处的计算结果应为 m[1][1] + m[2][2] + p[0]p[1]p[2].

Code Segment（Less important）

public class matrixChain {
    /***
     *
     * @param p 用于存放每个矩阵的维数（每个矩阵对应的行和列）
     * @param m 一个二维数组，用于存放计算某一个矩阵链所需的【连乘积】的次数
     * @param s 还是一个二维数组，用于存放矩阵链Ai···Aj的断裂点（k的位置）
     * @return
     */
    public static int solution(int[]p,int[][]m,int[][]s){
        int n=p.length-1;//矩阵个数
        for(int r=2;r<=n;r++){
            for(int i=1;i<=n-r+1;i++){
                int j=i+r-1;
                m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
                s[i][j]=i;
                for(int k=i+1;k<j;k++){
                    int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if(temp<m[i][j]){
                        m[i][j]=temp;
                        s[i][j]=k;
                    }
                }
            }
        }
        return m[1][n];
    }

    public static void traceback(int i, int j, int[][] s) {
        // 输出A[i:j] 的最优计算次序
        if (i == j) {
            // 递归出口
            System.out.print("A"+i);
            return;
        } else {
            System.out.print("(");
            // 递归输出左边
            traceback(i, s[i][j], s);
            // 递归输出右边
            traceback(s[i][j] + 1, j, s);
            System.out.print(")");
        }
    }

    public static void main(String[] args) {
        int[] p = new int[]{5,200, 2, 100, 30, 200};
        int[][] m=new int[p.length][p.length];
        int[][] s=new int[p.length][p.length];
        int result=matrixChain.solution(p,m,s);
        System.out.println(result);
        traceback(1, p.length-1, s);
    }

}