1130. 叶值的最小代价生成树

题目链接：1130. 叶值的最小代价生成树

方法：dp

解题思路

• 状态表示
  • 集合：\(dp[i][j]\) 表示子数组 \([i, j]\) 能构成的所有合法的二叉树集合；
  • 属性：\(dp[i][j]\) 的值表示集合中，二叉树非叶节点值和的其中最小值。
• 状态计算
  • 集合划分：将子数组 \([i, j]\)，划分为 \([i, k]\) 和 \([k + 1, j]\) 对应的两个子集；
  • 计算：
    • \(i = j，dp[i][j] = 0\)；
    • \(i\ != j，dp[i][j] = \min\limits_{k = i}^{j - 1}\{dp[i][k] + dp[k + 1][j] + mx[i][k] * mx[k + 1][j]\}\)。

代码

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 4)), mx(n, vector<int>(n));
        for (int i = 0; i < n; i ++ ) dp[i][i] = 0;
        for (int i = n - 1; i >= 0; i -- ) {
            mx[i][i] = arr[i];
            for (int j = i + 1; j < n; j ++ ) {
                mx[i][j] = max(arr[j], mx[i][j - 1]);
                for (int k = i; k < j; k ++ ) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mx[i][k] * mx[k + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

复杂度分析

时间复杂度：\(O(n^3)\)；
空间复杂度：\(O(n^2)\)。