答案：选D
运行结果：
m value is:
0,15750,7875,9375,
0,0,2625,4375,
0,0,0,750,
0,0,0,0,
s value is:
0113
0023
0003
0000
The result is:
((A1(A2A3））A4）
主要代码：
public class Nowcoder20150929 {
//N表示矩阵的个数
public static final int N = 4;
public static void main(String[] args) {
//由于矩阵相乘的特性p的长度为N+1
int[] datas = new int[] { 30, 35, 15, 5, 10 };
//m[i][j]表示的是i~j矩阵对应的最小计算代价
int[][] m = new int[N + 1][N + 1];
//s[i][j]表示的是在m[i][j]情况下的分割点
int[][] s = new int[N + 1][N + 1];
int i, j;
matrix_chain_order(datas, m, s);
//打印最小计算代价
System.out.println("m value is:");
for (i = 1; i <= N; ++i) {
for (j = 1; j <= N; ++j) {
System.out.print(m[i][j] + ",");
}
System.out.println();
}
System.out.println("s value is:");
for (i = 1; i <= N; ++i) {
for (j = 1; j <= N; ++j) {
System.out.print(s[i][j]);
}
System.out.println();
}
System.out.println("The result is:");
print_optimal_parents(s, 1, N);
}
private static void print_optimal_parents(int[][] s, int
i, int j) {
if (i == j) {
System.out.print("A" + i);
} else {
System.out.print("(");
print_optimal_parents(s, i, s[i][j]);
print_optimal_parents(s, s[i][j] + 1, j);
System.out.print("）");
}
}
private static void matrix_chain_order(int[] p, int[][]
m, int[][] s) {
int i, j, k, t;
for (i = 0; i <= N; ++i){
//i~i上只有一个矩阵，所以计算量为0
m[i][i] = 0;
}
for (t = 2; t <= N; t++) // 当前链乘矩阵的长度
{//t表示的是后一个矩阵
for (i = 1; i <= N - t + 1; i++) //
从第一矩阵开始算起，计算长度为t的最少代价
{//i表示的是前一个矩阵
j = i + t - 1;// 长度为t时候的最后一个元素
m[i][j] = Integer.MAX_VALUE; // 初始化为最大代价
for (k = i; k <= j - 1; k++) //
寻找最优的k值，使得分成两部分k在i与j-1之间
{
int temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] *
p[j];
if (temp < m[i][j]) {
m[i][j] = temp; // 记录下当前的最小代价
s[i][j] = k; // 记录当前的括号位置，即矩阵的编号
}
}
}
}
}
}
