矩阵连乘（动态规划）

题目描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如：

　　A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ;

最后的结果为：((A1(A2A3))((A4A5)A6)) 最小的乘次为15125。

思路：动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算（即先从最小的开始计算）。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。

public class Test {
    private static final int  count = 6;
    /**
     * 存储的是i+1到j+1的最小乘次，因为是从0开始
     */
    static int[][] min_part = new int[count][count];

    /**
     * 计算矩阵最小乘次数
     * @param p 保存矩阵行列的数组
     * @param n 矩阵的个数
     * @param min_part 保存最小乘次数
     * @return
     */
    public static int function(int[] p, int n, int[][]min_part) {
        int j = 0;

        for (int i = 0; i < n; i++) {
            min_part[i][i] = 0;
        }

        //r为连乘矩阵的个数
        for (int r = 2; r <= n; r++) {
            //i表示连乘矩阵的第一个,从连乘矩阵个数为2开始计算 需要算n-r个
            for (int i = 0; i <= n - r; i++) {
                //j表示连乘矩阵中的最后一个
                j = i + r - 1;
                min_part[i][j] = Integer.MAX_VALUE;

                for (int k = i; k <= j-1; k++) {
                    //在第一个与最后一个之间寻找最合适的断开点
                    int tmp = min_part[i][k] + min_part[k+1][j] + p[i]*p[k+1]*p[j+1];

                    if (tmp < min_part[i][j]) {
                        min_part[i][j] = tmp;
                    }
                }
            }
        }
        return min_part[0][n-1];
    }

    public static void main(String[] args) {
        int[] p = new int[count+1];
        p[0] = 30;
        p[1] = 35;
        p[2] = 15;
        p[3] = 5;
        p[4] = 10;
        p[5] = 20;
        p[6] = 25;

        int ans = function(p,count,min_part);
        System.out.println(ans);
    }
}

从2个矩阵开始计算: m[0][1] m[1][2] m[2][3] m[3][4] m[4][5] //m[0][1]表示第一个矩阵与第二个矩阵的最小乘次数、

以此类推 3个矩阵计算m[0][2] m[1][3] m[2][4] m[3][5]
。。。
一直到6个矩阵计算 m[0][5]即为结果

每次计算均取到上一矩阵计算保存的结果