牛客234249题最优二叉树构建：区间DP解法详解与代码实现

一、问题背景

牛客234249题要求我们根据给定的节点分数数组，构建一棵加分最大的二叉树。每个节点的加分计算规则为：左子树加分 × 右子树加分 + 当前节点分数。本文将详细解析使用区间动态规划(DP)解决该问题的完整思路。

二、核心算法解析

解决方案采用区间DP算法，主要分为三个关键步骤：

1. DP表初始化：建立dp表存储区间最优值，root表记录根节点位置

2. 区间递推计算：从小到大枚举区间长度，计算所有可能分割点

3. 前序遍历重构：根据root表重建最优二叉树结构

三、完整代码实现（带详细注释）

class Solution {
public:
    vector<vector<int>> scoreTree(vector<int>& scores) {
        int n = scores.size();
        // dp[i][j]表示区间i到j的最大加分
        vector<vector<int>> dp(n+2, vector<int>(n+2, 0));
        // root[i][j]记录区间i到j的根节点位置
        vector<vector<int>> root(n+2, vector<int>(n+2, 0));
        // 结果数组：result[0]存储最大加分，result[1]存储前序遍历序列
        vector<vector<int>> result(2);
        
        // 初始化单个节点情况（区间长度为1）
        for(int i = 1; i <= n; i++) {
            dp[i][i] = scores[i-1];  // 单个节点的加分就是自身分数
            root[i][i] = i;          // 单个节点的根就是自己
        }
        
        // 区间DP计算最大加分（从区间长度2开始逐步扩大）
        for(int len = 2; len <= n; len++) {
            for(int i = 1; i <= n-len+1; i++) {
                int j = i + len - 1;
                // 尝试所有可能的分割点k
                for(int k = i; k <= j; k++) {
                    // 左子树加分（k为左边界时设为1）
                    int left = (k == i) ? 1 : dp[i][k-1];
                    // 右子树加分（k为右边界时设为1）
                    int right = (k == j) ? 1 : dp[k+1][j];
                    // 当前分割点的加分值
                    int current = left * right + scores[k-1];
                    
                    // 更新最优解
                    if(current > dp[i][j]) {
                        dp[i][j] = current;
                        root[i][j] = k;
                    }
                }
            }
        }
        
        // 前序遍历重构二叉树结构
        vector<int> traversal;
        function<void(int, int)> preorder = [&](int l, int r) {
            if(l > r) return;
            traversal.push_back(root[l][r]);          // 访问根节点
            preorder(l, root[l][r]-1);                // 递归左子树
            preorder(root[l][r]+1, r);                // 递归右子树
        };
        preorder(1, n);
        
        // 构造返回结果
        result[0].push_back(dp[1][n]);  // 最大加分值
        result[1] = traversal;          // 前序遍历序列
        return result;
    }
};

四、关键点解析

1. 区间DP的填表顺序：必须按区间长度从小到大计算，确保子问题先被解决

2. 边界处理：当k为区间端点时，空子树的加分设为1（乘法单位元）

3. 时间复杂度：O(n³) 三重循环，空间复杂度O(n²)

4. 重构树结构：利用root表通过前序遍历即可重建最优二叉树