本文涉及的基础知识点

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 位带符号整数，即小于 2³¹ 。

记忆化搜索

n = arr.length
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。$⟺$ 将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);
		}

单调栈

本题就是临项消除：消除成本是两项的乘积，合并后的项是两者的较大者。
证明难度太大，建议暂且放一放。孤立的知识点，难学易忘，效率低得发指