区间dp
2026-01-24 13:07:19
发布于:浙江
区间型动态规划是线性动态规划的一种扩展,其表现形式一般为:给定直线(或环)上一组的点,每个点均有特定的权值(为整数或浮点数),要求选取若干点作为分界点,以便将这些点划分为若干个部分。选取不同的分界点有不同的代价,要求确定一种最优的划分方法,使得代价的总和最优(即使得代价最小或最大)。
由于树结构的特殊性,可以很方便地应用动态规划的思维——父结点的最值取决于其子结点的最值,令 dp[u] 表示结点 u 的最值,w[u] 表示选择结点 u 的代价,那么树形动态规划的递推关系式一般为
dp[u] = max/min{dp[v]} + w[u]
(其中 {parent[v]=u} 表示对所有以 u 为父结点的子结点 v 进行 max/min 操作)。
全部评论 1
?
1周前 来自 广东
0

















有帮助,赞一个