本文涉及的基础知识点
C++单调栈
C++记忆化搜索
C++动态规划
LeetCode1130. 叶值的最小代价生成树
给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：
每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
如果一个节点有 0 个子节点，那么该节点为叶节点。
示例 1：
输入：arr = [6,2,4]
输出：32
解释：有两种可能的树，第一种的非叶节点的总和为 36 ，第二种非叶节点的总和为 32 。
示例 2：
输入：arr = [4,11]
输出：44
提示：
2 <= arr.length <= 40
1 <= arr[i] <= 15
答案保证是一个 32 位带符号整数，即小于 231 。
记忆化搜索
n = arr.length
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。 ⟺ \iff ⟺ 将arr分成左右两部分,arr1,arr2，arr1对应左子树,arr2对应右子树。
如果arr只有一个元素，其最小和为arr[0]。
否则拆分arr1,arr2，递归处理。两这皆不能为空。
动态规划的状态记录
dp[i][j] 记录arr[i…j]对应的子树最小和。空间复杂度：O(nn)
动态规划的状态方程
dp[i][j] = min k = i j − 1 \min_{k=i}^{j-1} mink=ij−1(dp[i][k]+dp[k+1][j]) + arr[i…j]之积。arr[i…j]之积 可以预处理，也可以用前缀和。由于答案在int32范围内，故arr之积也在int32范围内。
单个状态的时间复杂度：O(n)
总时间复杂度：O(nnn) 注意：dp[i][j]的状态记录下来，初始-1，如果是-1则计算，否则查询。
初始调用
Cal(0,arr.lenght-1）
代码
核心代码
class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
m_arr = arr;
m_dp.assign(arr.size(), vector<int>(arr.size(),-1));
m_max.assign(arr.size(), vector<int>(arr.size(), 0));
for (int i = 0; i < arr.size(); i++) {
m_max[i][i] = arr[i];
for (int j = i + 1; j < arr.size(); j++) {
m_max[i][j] = max(arr[j], m_max[i][j - 1]);
}
}
return Cal(0, arr.size() - 1);
}
int Cal(int left, int r) {
if (-1 != m_dp[left][r]) { return m_dp[left][r]; }
if (left == r) {
return m_dp[left][r] = 0;
}
int iMin = INT_MAX;
for (int i = left; i < r; i++) {
iMin = min(iMin, Cal(left, i) + Cal(i + 1, r)+ m_max[left][i]* m_max[i+1][r]);
}
return m_dp[left][r] = iMin ;
}
vector<vector<int>> m_dp,m_max;
vector<int> m_arr;
};
单元测试
vector<int> arr;
TEST_METHOD(TestMethod11)
{
arr = { 6,2,4 };
auto res = Solution().mctFromLeafValues(arr);
AssertEx(32, res);
}
TEST_METHOD(TestMethod12)
{
arr = { 4,11 };
auto res = Solution().mctFromLeafValues(arr);
AssertEx(44, res);
}
单调栈
本题就是临项消除：消除成本是两项的乘积，合并后的项是两者的较大者。
证明难度太大，建议暂且放一放。孤立的知识点，难学易忘，效率低得发指
