【牛客234249题解析】评分树问题：动态规划与递归遍历的解题思路与代码实现
一、题目解读
牛客234249题要求构建一棵评分树，通过给定的分数数组计算最大加分路径，并返回路径节点及总分。题目核心在于如何将区间动态规划与树结构遍历结合，寻找最优解。理解题目需把握“评分规则”与“树形结构”的关系，即通过节点分割区间，计算子区间乘积与得分之和的最大值。
二、解题思路
采用动态规划（Dynamic Programming）与递归遍历的策略。首先通过区间DP计算任意区间内的最大得分及对应根节点，再利用前序遍历构建树结构。关键在于：
1. 定义二维DP数组存储区间最大得分和根节点索引。
2. 初始化单个节点为自身得分，逐步扩展区间长度求解。
3. 递归函数实现前序遍历，记录根节点路径。
三、解题步骤
1. 初始化：创建dp（得分矩阵）、root（根节点矩阵）、result（最终结果容器）。单个节点得分即原始分数，根节点为自己。
2. 区间DP计算：
外层循环控制区间长度（len=2~n），内层循环遍历起始位置。
对每个区间，枚举分割点k，计算左右子区间的乘积与当前得分，更新最大值及对应根节点。
3. 前序遍历构建路径：
定义递归函数preorder(l, r)，通过root[l][r]确定当前区间的根节点，递归左子树和右子树。
将根节点加入traversal列表，最终形成前序遍历序列。
4. 结果构造：将总分存入result[0]，路径存入result[1]并返回。
四、代码与注释
class Solution {
public:
vector<vector<int>> scoreTree(vector<int>& scores) {
int n = scores.size();
vector<vector<int>> dp(n+2, vector<int>(n+2, 0)); // 区间最大得分
vector<vector<int>> root(n+2, vector<int>(n+2, 0)); // 区间根节点
vector<vector<int>> result(2); // 最终结果：总分与路径
// 初始化单个节点情况
for(int i = 1; i <= n; i++) {
dp[i][i] = scores[i-1]; // 得分即原始分数
root[i][i] = i; // 根节点为自己
}
// 区间DP计算最大加分
for(int len = 2; len <= n; len++) { // 区间长度
for(int i = 1; i <= n-len+1; i++) { // 起始位置
int j = i + len - 1; // 结束位置
for(int k = i; k <= j; k++) { // 枚举分割点
int left = (k == i)? 1 : dp[i][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;
}
};注释说明：代码中已标注关键逻辑，包括初始化、DP状态转移方程、递归遍历的实现细节，帮助读者理解算法核心。
五、总结
该解法巧妙运用区间DP解决最优子结构问题，通过记录根节点避免重复计算，递归遍历高效构建树路径。在算法竞赛或实际应用中，动态规划与树结构结合的思路具有广泛适用性。需注意边界处理（如单节点特例）和递归终止条件，确保正确性与效率。此外，代码结构清晰，注释明确，可作为类似问题的参考模板。
原创内容 转载请注明出处
