移除 wordpress 评论的,肇庆seo,即墨网站设计,饰品销售网站功能建设1130. 叶值的最小代价生成树 难度#xff1a;中等 力扣地址#xff1a;https://leetcode.cn/problems/minimum-cost-tree-from-leaf-values/description/ 题目内容
给你一个正整数数组 arr#xff0c;考虑所有满足以下条件的二叉树#xff1a;
每个节点都有 0 个或是 2 个…1130. 叶值的最小代价生成树 难度中等 力扣地址https://leetcode.cn/problems/minimum-cost-tree-from-leaf-values/description/ 题目内容
给你一个正整数数组 arr考虑所有满足以下条件的二叉树
每个节点都有 0 个或是 2 个子节点。 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。 在所有这样的二叉树中返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
如果一个节点有 0 个子节点那么该节点为叶节点。
示例 1 输入arr [6,2,4] 输出32 解释有两种可能的树第一种的非叶节点的总和为 36 第二种非叶节点的总和为 32 。 示例 2 输入arr [4,11] 输出44 提示
2 arr.length 401 arr[i] 15答案保证是一个 32 位带符号整数即小于 2 31 2^{31} 231 。
解题过程 1 —— 小白的思考流程 由于本人能力有限木有做出来。此处主要参考了官方的解题过程结合自己的理解记录一下。 题目看起来很复杂实际上也不简单。这里我们首先使用比较直观的方法求解列举所有可能并起初结果然后返回最小的。如例1所示这里我们先把两种情况画出来就知道哪个结果更小了。
即输入 6 2 4 时有可能的结果是 6 * 4 2 * 4 32也有可能是 6 * 4 2 * 6 36。 这里我们定义一个函数用来求解三个结点时的最优结果。
int calculate(int a, int b, int c) {// 如果 d1 较小则选择让 a 与 b 结合成为兄弟结点int d1 (a * b) max(a, b) * c;// 如果 d2 较小则选择让 b 与 c 结合int d2 (b * c) max(b, c) * a;return min(d1, d2);
}接着我们需要思考的问题是如果超过3个结点该如何应对
比如现在的输入是 [6,4,5,1]最终的结果是 55计算方法是 这种情况下我们发现 5 和 1 是兄弟结点然后 5与1 的结合结果与 4 是兄弟结点而 6 与它们仨的结合体是兄弟节点。
这里我们应当把其他情况也列一下 这个时候我们可以发现这些结果也就是 calculate(a, b, c) 得到结果 d1 然后再 将 d1 与 d 重新计算或者计算 calculate(b, c, d) 得到 d2然后再计算 d2 与 a 的结果。
结论1总而言之我们需要划分也就是分治过程。
接下来我们可以开始处理更加复杂的情况了如果总共有 5 个结点我们可以先将前3个看为一个整理然后与第4个与第5个计算得到结果也可以 ……
这里我们直接强行计算所有情况。
接下来需要考虑左右子树的划分过程前面给出的例子中[6, 4, 2, 1] 可以分为三种情况1 3左子树1个右子树3个2 2 左右子树各一个以及 3 1 左子树3个右子树1个。
类似地如果更多结点我们需要考虑这种左右子树的划分过程并且根据每种情况计算结果。
结论2需要考虑所有的左右子树划分情况循环遍历所有可能。
开始写代码
class Solution {
public:int mctFromLeafValues(vectorint arr) {int n arr.size();// dp[i][j] 表示从 arr[i] 到 arr[j] 构成的子树的非叶节点值的最小总和vectorvectorint dp(n, vectorint(n, INT_MAX / 4));// maxVal[i][j] 表示从 arr[i] 到 arr[j] 之间的最大值vectorvectorint maxVal(n, vectorint(n));for (int j 0; j n; j) {// 计算 arr[i] 到 arr[j] 之间的最大值。// maxVal[i][j - 1] 是子数组 arr[i] 到 arr[j-1] 的最大值。// 新加入的元素是 arr[j]所以 maxVal[i][j] 是 maxVal[i][j - 1] 和 arr[j] 中的较大值。// 当只有一个元素时最大值就是元素本身maxVal[j][j] arr[j];// 单个节点没有非叶节点值为 0dp[j][j] 0;for (int i j - 1; i 0; i--) {// 更新 maxVal[i][j] 为子数组 arr[i] 到 arr[j] 的最大值maxVal[i][j] max(arr[i], maxVal[i 1][j]);// 枚举分割点 k将子数组分为 arr[i] 到 arr[k] 和 arr[k 1] 到 arr[j]for (int k i; k j; k) {// 更新 dp[i][j] 为分割后子树的最小非叶节点值总和dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] maxVal[i][k] * maxVal[k 1][j]);}}}return dp[0][n - 1];}
};时间复杂度 O ( n 3 ) O(n^3) O(n3) 空间复杂度 O ( n 2 ) O(n^2) O(n2)
方法总结 动态规划的核心 在于通过解决子问题来解决更大规模的问题。我们通过定义 dp[i][j] 来表示子数组 arr[i] 到 arr[j] 的最小非叶节点值的总和这样我们可以逐步从小规模问题解决到大规模问题。 分治法的核心思想 是将一个大问题分解成若干个小问题分别解决然后将小问题的解组合成大问题的解。在这个问题中我们通过枚举分割点 k 来将子数组 arr[i] 到 arr[j] 分成两部分即 arr[i] 到 arr[k] 和 arr[k1] 到 arr[j]然后分别解决这两部分子问题最后将它们的解组合起来。
具体来说分治思想体现在
分解将子数组 arr[i] 到 arr[j] 分成两部分即 arr[i] 到 arr[k] 和 arr[k1] 到 arr[j]。解决分别解决这两个子问题即计算 dp[i][k] 和 dp[k1][j]。合并将两个子问题的解 dp[i][k] 和 dp[k1][j] 合并同时加上当前划分下的非叶节点值 maxVal[i][k] * maxVal[k1][j]。 Smileyan 2024.06.23 00:27
