加分二叉树

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param scores int整型ArrayList
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> scoreTree (ArrayList<Integer> scores) {
        ArrayList<Integer> pre = new ArrayList<>();
        Node[][] dp = new Node[scores.size() + 1][scores.size() + 1];
        Node root = buildMaxScoreTree(scores, 0, scores.size(), dp);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int s = root.addScore;
        ArrayList<Integer> scoreList = new ArrayList<>();
        scoreList.add(s);
        res.add(scoreList);
        visitNode(root, pre);
        res.add(pre);
        return res;
    }

    private void visitNode(Node node, ArrayList<Integer> pre) {
        if (node == null) {
            return;
        }
        pre.add(node.nodeIndex);
        visitNode(node.left, pre);
        visitNode(node.right, pre);
    }

    private static class Node {
        private int nodeIndex;
        private int addScore;
        private int score;
        private Node left;
        private Node right;
    }

    private Node buildMaxScoreTree(ArrayList<Integer> scores, int index,
                                   int nodeNum, Node[][] dp) {
        if (dp[index][nodeNum] != null) {
            return dp[index][nodeNum];
        }
        if (nodeNum == 0) {
            return null;
        }
        Node node = new Node();
        if (nodeNum == 1) {
            node.score = scores.get(index);
            node.addScore = scores.get(index);
            node.nodeIndex = index + 1;
            dp[index][nodeNum] = node;
            return node;
        }
        int maxScore = 0;
        Node maxLeft = null;
        int nodeIndex = 0;
        Node maxRight = null;
        int mscore = 0;
        for (int i = 0; i < nodeNum; i++) {
            Node left = buildMaxScoreTree(scores, index, i, dp);
            int leftScore = left == null ? 1 : left.addScore;
            int score = scores.get(index + i);
            int rightNodeNum = nodeNum - i - 1;
            Node right = buildMaxScoreTree(scores, index + i + 1, rightNodeNum, dp);
            int rightScore = right == null ? 1 : right.addScore;
            int theAddScore = leftScore * rightScore + score;
            if (theAddScore > maxScore) {
                maxLeft = left;
                maxRight = right;
                maxScore = theAddScore;
                mscore = score;
                nodeIndex = index + i + 1;
            }
        }
        node.addScore = maxScore;
        node.left = maxLeft;
        node.right = maxRight;
        node.score = mscore;
        node.nodeIndex = nodeIndex;
        dp[index][nodeNum] = node;
        return node;
    }

}