动态问题求解步骤

  • 分析最优解的结构

  • 建立递归关系

  • 计算最优解

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

  • 动态规划

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

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

      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());
}
}