使用kotlin解决这个问题：1130. 叶值的最小代价生成树 提示 中等 311 相关企业 给你一个正整数数组 arr，考虑所有满足以下条件的二叉树： 每个节点都有 0 个或是 2 个子节点。 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。 在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。 如果一个节点有 0 个子节点，那么该节点为叶节点。

这道题可以使用动态规划来解决。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从第 i 个数到第 j 个数（包括 i 和 j）所能构成的最小代价生成树的总和。对于每个区间 [i, j]，我们可以枚举其所有可能的根节点 k，然后将其分成两部分 [i, k] 和 [k+1, j]，分别计算其子树的最大叶节点值的乘积，然后加上这个根节点的代价 arr[k]，得到这个区间的总代价。最后，我们可以在所有可能的中取最小值。

具体实现如下：

fun mctFromLeafValues(arr: IntArray): Int {
    val n = arr.size
    val maxLeaf = Array(n) { IntArray(n) }
    for (i in 0 until n) {
        var max = arr[i]
        for (j in i until n) {
            max = maxOf(max, arr[j])
            maxLeaf[i][j] = max
        }
    }
    val dp = Array(n) { IntArray(n) }
    for (len in 2..n) {
        for (i in 0..n-len) {
            val j = i + len - 1
            dp[i][j] = Int.MAX_VALUE
            for (k in i until j) {
                dp[i][j] = minOf(dp[i][j], dp[i][k] + dp[k+1][j] + maxLeaf[i][k] * maxLeaf[k+1][j])
            }
        }
    }
    return dp[0][n-1]
}

时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。