矩阵链乘

动态问题求解步骤

• 分析最优解的结构

• 建立递归关系

• 计算最优解

• 矩阵可乘的条件是矩阵A的列数等于矩阵B的行数

• 动态规划

  • 不能用三角形进行求解 环环相扣 选择其他一个会对其他结果造成影响

  • 三层for 转移方程：m[i][j]
    i == j , m = 0
    i < j , min(m[i][k] , m[k+1][j] ) + p_i-1p_kp_j
    

    public class Matrix_multiplication {
    public static void main(String[] args) {
     int[] A = {5,200,2,100,30,200};
     int point[][] = new int [A.length][A.length];
     System.out.println(matrix_multiplication(A,point));
     traceback(point);
    }
    
    public static int matrix_multiplication(int p [],int point[][] ) {
     int len = p.length-1;                                 //加入了标记锚点
     int [][]f = new int [len+1][len+1];
     for(int i = 1 ; i <= len ; i++) {                      //虽然创建的时候就已经初始化了
         f[i][i] = 0; 
         point[i][i] = i;
      }
     for(int r = 2; r <= len ; r++)                       // 所有长度为2....len全部求解出来
         for(int i = 1 ; i<= len- r + 1 ;i++) {              //起点是1 长度为 r
             int j = i + r - 1 ;                             //对应长度的终点 j
             f[i][j] = f[i+1][j] + p[i-1]*p[i]*p[j];         //这里可以定义成Integer.Max_VALUE;
             point[i][j] = i;
             for(int k = 1 ; k+i < j  ; k++) {             //截点k+i
                 int temp = f[i][k+i] + f[k+i+1][j] +  p[i-1]*p[k+i]*p[j]; //仅需要三个数即可
                 if(temp<f[i][j]) {
                     f[i][j] = temp;
                     point[i][j] = k;
                 }
             }
         }
         for(int i = 1 ; i < f.length ; i++){
             for(int j = 1 ; j < f.length ; j++){
                 System.out.printf("%9d",f[i][j]);
                 //带正负号输出，且符号占用一个长度，9代表输出的长度，5代表小数点后的位数
             }System.out.print("\n");
         }
     return f[1][len];
    }
    public static void traceback(int [][]s ) {
     StringBuffer sbf = new StringBuffer("");
     int temp = 0;
     for(int i = 0 ; i < s.length ;i++) {
         for(int j = 0 ; j < s.length ; j++) {
             System.out.print(s[i][j]+" ");
         }System.out.println();
     }
     System.out.println(sbf.toString());
    }
    }