题解 | #矩阵乘法计算量估算#

(A(BC))的计算过程：

1.while循环处理最内层括号，取出第一个子串为BC

2.调用递归函数计算BC，计算结果用a替换，变为(Aa)，同时将a送入HashMap中，A的value在HashMap中是二维数组{行，列}，而a是三维数组{行，列，相乘次数}

3.while循环处理剩余括号，取出子串Aa

4.调用递归函数计算Aa

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main me = new Main();
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int n = Integer.parseInt(in.nextLine());
		  //把矩阵放在HashMap中，key为char型的矩阵名称，val为数组{矩阵的行数，矩阵的列数}
            HashMap<Character, int[]> nn = new HashMap<>();
            for (int i = 0; i < n; i++) {
                int temp[] = Arrays.stream(in.nextLine().split(" ")).mapToInt(
                                 c-> Integer.parseInt(c)).toArray();
                char key = (char) ('A' + i);
                nn.put(key, temp);
            }
            String s = in.nextLine();
            char ress = 'a';//用小写字母来表示子串计算完成后所得的矩阵
		  //处理字符串中的括号
            while (s.contains("(")) {
                int f1 = s.lastIndexOf("(");
                int e1 = s.indexOf(")", f1);
                String snow = s.substring(f1 + 1, e1);
			  //每次取一个（）中的子串进行计算，将子串返回结果做一个三元数组也放在hashmap中
                nn.put(ress, me.cishu(snow, nn, new int[] {0, 0, 0}));
                String sleft = f1 == 0 ? "" : s.substring(0, f1);
                String sright = e1 == s.length() - 1 ? "" : s.substring(e1 + 1);
                s = sleft + ress + sright;//更新s，用字串的计算结果（用小写字母表示）替换掉原来的子串
                ress += 1;
            }
            if (s.length() == 1) {
                System.out.println(nn.get(s.charAt(0))[2]);
            } else {
                System.out.println(me.cishu(s, nn, new int[] {0, 0, 0})[2]);
            }

        }
    }
  //递归算法计算不带括号的时候相乘次数，返回结果放在一个三元数组-{结果矩阵的行数，结果矩阵的列数，相乘次数}，start为初始矩阵，每次用start*子串第一个字母所代表的矩阵，例如子串BC，第一次就是start*B
    int[] cishu(String s, HashMap<Character, int[]> ff, int[] start) {
        if (s.length() == 0) {
            return start;
        } else {
            char nowc = s.charAt(0);
            int[] nows = ff.get(nowc);//当前要相乘的矩阵
            s = s.length() == 1 ? "" : s.substring(1);//更新s，作为递归的输入
            int ress[];
		  //当前矩阵可能是以前子串的计算结果例如(A(BC))经过第一次计算后变成（Aa),此时的a是三元组第三个元素是相乘次数，那就要加上这个次数
            int nownums = nows.length == 3 ? nows[2] : 0;
            if (Arrays.equals(start, new int[] {0, 0, 0})) {//当start矩阵元素都为0时，代表现在是子串的第一个矩阵，那么应该以它本身的行数列数为初始矩阵进入递归
                ress = cishu(s, ff, new int[] {nows[0], nows[1], nownums});
            } else {//当start矩阵元素不为0时，start是递归返回的结果，那么就计算start*nows
                int res = start[2] + start[0] * start[1] * nows[1];
                ress = cishu(s, ff, new int[] {start[0], nows[1], nownums + res});
            }
            return ress;
        }
    }
}