做网站在哪儿买空间,网络运维工程师需要学什么,做网站创业需要注册公司吗,网页升级紧急通知区域1.代码
public class MatrixChainMultiplication {public static void main(String[] args) {
// 在该代码中#xff0c;我们首先创建了两个n * n的矩阵m和s#xff0c;分别用于记录最优值和分割点。 其中m 矩阵 通过i j 来显示在i到j的矩阵链中最优解
//
// …1.代码
public class MatrixChainMultiplication {public static void main(String[] args) {
// 在该代码中我们首先创建了两个n * n的矩阵m和s分别用于记录最优值和分割点。 其中m 矩阵 通过i j 来显示在i到j的矩阵链中最优解
//
// 然后我们将i j时的m[i][j]赋值为0因为一个矩阵的乘积为0。
//
// 接下来我们使用L循环枚举子问题规模i循环枚举左端点j循环枚举右端点并使用k循环枚举分割点。
//
// 对于每个分割点k我们计算最优值q然后将q与m[i][j]进行比较如果q小于m[i][j]则更新m[i][j]和s[i][j]。
// 通过公式算法导论15.7
//
// 最后我们返回m[1][n-1]即原问题的最优值。
//
// 该算法的时间复杂度为O(n^3)其中n是矩阵的数量。int[] p {30, 35, 15, 5, 10, 20, 25};System.out.println(最少的乘法次数为 matrixChainOrder(p));}
public static int matrixChainOrder(int[] p) {int n p.length;// 创建n * n的矩阵m和s用于记录最优值和分割点int[][] m new int[n][n];int[][] s new int[n][n];// ij时m[i][j]0因为一个矩阵的乘积为0for (int i 1; i n; i) {m[i][i] 0;}for (int i 0; i m.length; i) {System.out.println(Arrays.toString(m[i]));}
// L是子问题规模for (int L 2; L n; L) {// i是左端点j是右端点k是分割点for (int i 1; i n - L 1; i) {int j i L - 1;m[i][j] Integer.MAX_VALUE;// 枚举分割点k求解最优值for (int k i; k j; k) {int q m[i][k] m[k 1][j] p[i - 1] * p[k] * p[j];System.out.println(m[i][k]: m[i][k] );System.out.println(m[k 1][j]: m[k 1][j]);System.out.println(i:i k:k j:j);System.out.println(q);if (q m[i][j]) {m[i][j] q;s[i][j] k;}}}}// 返回最优值return m[1][n - 1];}
}
2.原理
自己看算法导论吧
我再看到 这条公式的时候很困惑,然后自己手算了他给的第一个例子才知道这是正确的.
3.问题
具体的问题已经在代码注释中讲解完毕
4.进阶
输出只是I一个普通的递归而已
package collection;
public class printOptimalParens {public static void matrixChainOrder(int[] p) {int n p.length - 1;int[][] m new int[n 1][n 1];int[][] s new int[n 1][n 1];for (int i 1; i n; i) {m[i][i] 0;}for (int len 2; len n; len) {for (int i 1; i n - len 1; i) {int j i len - 1;m[i][j] Integer.MAX_VALUE;for (int k i; k j - 1; k) {int q m[i][k] m[k 1][j] p[i - 1] * p[k] * p[j];if (q m[i][j]) {m[i][j] q;s[i][j] k;}}}}System.out.println(Optimal Parenthesization:);printOptimalParens(s, 1, n);}
public static void printOptimalParens(int[][] s, int i, int j) {if (i j) {System.out.print(A i);} else {System.out.print(();printOptimalParens(s, i, s[i][j]);printOptimalParens(s, s[i][j] 1, j);System.out.print());}}
public static void main(String[] args) {int[] p {30, 35, 15, 5, 10, 20, 25};matrixChainOrder(p);}
}
((A1(A2A3))((A4A5)A6))
