题目：叶值的最小代价生成树

给你一个正整数数组arr，考虑所有满足以下条件的二叉树：
- 每个节点都有 0 个或是 2 个子节点。
- 数组arr中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
- 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
- 在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个32 位整数。

示例：

输入：arr = [6,2,4]
输出：32
解释：
有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。
    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

提示：

2 <= arr.length <= 40
1 <= arr[i] <= 15
答案保证是一个 32 位带符号整数，即小于2^31。

来源：力扣（LeetCode）第1130题

链接：https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values

分析：

这道题有两种解法，一种是动态规划，另一种是使用单调栈。

代码：

动态规划：

我们发现数组中的数可以划分为两部分，一半是左子树，一半是右子树，根节点就是左边最大和右边最大的乘积。
而左右子树里面的值就是当数组中的数为左子树的叶子节点时的情况，右边一样。
直到数组中的数只有2个时，答案就是左边右边相乘。
因此我们可以这么看，如果2个数后面又加了一个数，那么我们可以以01为一个节点再和2划分,也可以0一个节点和12划分。
树的左右两边至少有1个叶子结点。
如果有四个数，有0 123, 01 23, 012 3,同时3个数又有之前的情况。
因此我可以这样找状态，i代表起始点,j代表结束位置。如果我想知道4个数的答案，我就把上面划分的情况算出来，每一个情况还要加上左边和右边的最大值的乘积，作为根节点。

于是乎我就是要穷举所有状态。

class Solution {
public int mctFromLeafValues(int[] arr) {
    int len = arr.length;
    int[][] dp = new int[len][len];
    int[][] maxVal = new int[len][len];
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            int max = 0;
            for (int k = i; k <= j; k++) if (max < arr[k]) max = arr[k];
            maxVal[i][j] = max;
        }
    }
    for (int i = 0; i < len; i++) for (int j = 0; j < len; j++) dp[i][j] = Integer.MAX_VALUE;
    for (int i = 0; i < len; i++) dp[i][i] = 0;
    for (int i = 1; i < len; i++) { // 长度
        for (int j = 0; j < len - i; j++) { // 起始点
            for (int k = j; k < j + i; k++) { // 中间点
                dp[j][j+i] = Math.min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + maxVal[j][k] * maxVal[k+1][j+i]);
            }
        }
    }
    return dp[0][len-1];
}
}

单调栈：

单调栈的方法有点讨巧。
以上是我的个人理解
我们维护一个单调递减栈，单调递减栈有一个特性。
如果我们遇到一个比栈顶元素大元素，于是乎就有了两种情况。
我们就看前面3个。
第一种情况：大小中，这样只会将小出栈。
我们来算一下：
- 大小放一块：大 * 小 + 大 * 中
- 小中放一块：小 * 中 + 大 * 中
- 所以把小和中放在一起得到的值更小。
第二种情况：中小大，小中都会出栈
- 中小放在一块：中 * 小 + 中 * 大
- 小大放在一块：小 * 大 + 中 * 大
- 因此把中小放在一起得到的值更小。
由此得出结论如果遇到出栈情况，我们将小的那个(也就是栈顶元素)和它左边或右边较小的那个放在一起得到的答案是最优。
同时，小的那个元素就不再需要了，我们只看大的那个元素可能还会和别的值相乘。

最后将值放入栈后，栈内元素单调递减，于是就有了大中小,这个可以自己去证。会发现还是把中小放在一起最优。

class Solution {
public int mctFromLeafValues(int[] arr) {
    Stack<Integer> stack = new Stack();
    stack.push(Integer.MAX_VALUE);
    int ans = 0;
    for (int n : arr) {
        while (stack.peek() < n) ans += stack.pop() * Math.min(stack.peek(), n);
        stack.push(n);
    }
    while (stack.size() > 2) ans += stack.pop() * stack.peek();
    return ans;
}
}