加分二叉树是 NOIP 经典区间 DP 题。

题目描述

给定一棵二叉树的中序遍历，每个节点有分数。求最大加分和对应的前序遍历。

解题思路

  • 状态定义：dp[i][j] = 中序区间 [i,j] 构成的最大加分
  • 状态转移：枚举根 k，左子树加分 乘以 右子树加分 加 根加分
  • 记录根节点：root[i][j] 记录区间 [i,j] 的最优根

常见错误

  • 初始状态处理错
  • 忘记记录根节点

咨询高级 DP 学习：151 6522 2880