1130. 叶值的最小代价生成树
2023-05-30 本文已影响0人
红树_
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
。