首页 > 代码库 > matrix_chain_order
matrix_chain_order
to calculate the min step of multiplicate some matixs
1 package dynamic_programming; 2 3 public class matrix_chain_order { //input is a sequence p = p0,p1..pn,where p.length = n+1 (matrix n is pn-1pn) 4 int[] p; 5 int[][] cost; 6 public matrix_chain_order(int[] a){ 7 p = a; 8 } 9 public int order(){ 10 int q = 0; 11 int n = p.length -1; 12 cost = new int[n][n]; 13 for(int i = 0;i<= n-1;i++){ 14 cost[i][i] = 0; 15 } 16 for(int l = 2;l<n;l++){ //the chain length,like merge sort 17 for(int i=0;i<n-l;i++){ 18 int j = i+l -1; 19 cost[i][j] =Integer.MAX_VALUE; 20 for(int k = i;k <=j -1;k++){ 21 q = cost[i][k] + cost[k+1][j] + p[i-1]*p[k]*p[j]; 22 if(q < cost[i][j]){ 23 cost[i][j] = q; //remeber the best step of i to j 24 } 25 } 26 } 27 } 28 return cost[n-1][n-1]; 29 } 30 31 32 }
matrix_chain_order
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。