1130. 叶值的最小代价生成树

LC每日一题，参考1130. 叶值的最小代价生成树。

题目

给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：

• 每个节点都有 0 个或是 2 个子节点。
• 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。
• 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积(叶节点的子节点数为0)。

在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。

输入：arr = [6,2,4]
输出：32
解释：有两种可能的树，第一种的非叶节点的总和为 36 ，第二种非叶节点的总和为 32 。 

解题思路

• 递归+记忆化搜索：考虑递归实现,用记忆化搜索优化。

递归+记忆化搜索

class Solution {
    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        int[][] max = new int[n][n]; // 定义一个二维数组来记录区间最大值
        for (int i = 0; i < n; i++) {
            int curMax = 0;
            for (int j = i; j < n; j++) {
                curMax = Math.max(curMax, arr[j]); // 求出[i,j]的最大值
                max[i][j] = curMax; // 记录[i,j]区间最大值
            }
        }
        return dfs(arr, 0, n - 1, max, new int[n][n]); // 从根节点开始递归
    }

    private int dfs(int[] arr, int start, int end, int[][] max, int[][] memo) {
        if (start == end) return 0; // 叶子节点，返回0
        if (memo[start][end] > 0) return memo[start][end]; // 如果当前结点已经被访问过，直接返回结果
        int res = Integer.MAX_VALUE;
        // 枚举分割点i
        for (int i = start; i < end; i++) {
            res = Math.min(res, dfs(arr, start, i, max, memo)
                + dfs(arr, i + 1, end, max, memo)
                + max[start][i] * max[i + 1][end]); // 左右子树+加上当前结点
        }
        return memo[start][end] = res; // 记录当前结点的计算结果
    }
}

复杂度分析

• 时间复杂度：O(n^3)，最大值前缀和为n^2,记忆化搜索状态个数n^2,单个状态计算时间n,总时间复杂度为T(n^2 + n^3) = O(n^3)。
• 空间复杂度：O(n^2)，前缀和和记忆化数组空间n^2。