Given an arrayarr
of positive integers, consider all binary trees such that:
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
- Each node has either
0
or2
children;- The values of
arr
correspond to the values of each leaf in an in-order traversal of the tree.- The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.
【動態規劃|1130. Minimum Cost Tree From Leaf Values(DP)】A node is a leaf if and only if it has zero children.
This is a typical interval DP question. The special place of this problem is a node's value depends on its leaf node's value.
So, we first store all the interval's maximum leaf node and then do a normal interval dp.
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxleaf[i][k] * maxleaf[k + 1][j])
class Solution {
public:
int mctFromLeafValues(vector& arr) {
//calculate the maxi leaf in every interval
int n = arr.size();
vector> maxLeaf(n, vector(n, 0));
for(int i = 0;
i < n;
i++)maxLeaf[i][i] = arr[i];
for(int i = 0;
i < n;
i++){
for(int j = i + 1;
j < n;
j++){
maxLeaf[i][j] = max(maxLeaf[i][j - 1], arr[j]);
}
}
vector> dp(n, vector(n, 0));
for(int len = 1;
len < n;
len++){
for(int j = 0;
j < n - len;
j++){
int end = j + len;
dp[j][end] = 1e8;
for(int k = j;
k < end;
k++){
dp[j][end] = min(dp[j][k] + dp[k + 1][end] + maxLeaf[j][k] * maxLeaf[k + 1][end], dp[j][end]);
}
}
}
return dp[0][n - 1];
}
};
推荐阅读
- 一起刷好题|《二叉树刷题计划》——平衡二叉树
- 动态规划|115、完全背包-LeetCode-139.单词拆分
- 大数据|大模型炼丹无从下手(谷歌、OpenAI烧了几百万刀,总结出这些方法论…)
- 云计算|云计算与大数据”研讨会(迎来新的科学价值)
- java|java简单版扫雷实现
- 算法|hash算法详解
- 开发人员最常见的10大C++错误
- 数据结构|凸包问题-Graham 算法
- 蓝桥杯|8.7结构体中const用法