本文共 557 字，大约阅读时间需要 1 分钟。

树形动态规划（Tree DP）是一种结合树结构特点的动态规划技术，常见于处理包含树结构的组合优化问题。与传统的线性或平面动态规划相比，树形DP的状态转移更复杂，需要结合树的层次结构来建立递推关系。

树形DP最初出现在典型的子树计数问题中，每个节点需要决定是否被选中，从而影响其子树的选择。状态设计通常会用 f[i][0] 和 f[i][1] 表示以节点 i 为根时，如果选中 i，那么它的子树可以选 j；如果不选中 i，则 dp[i][0] 会考虑选中或不选中 j 的最大宝物值。

这类问题通常需要从叶子节点开始递归计算到根节点。举例来说，如果有一个节点没有孩子，它的 dp[i] 数组只需设为其宝物值。随后，每个非叶子节点会根据子节点的 dp 值进行状态更新，最终反馈给父节点。

中国曲奇问题是一种结合背包概念的树形DP应用。每个城堡可以传递一个取中不了的约束条件，这使得问题复杂度明显升级。解决方案是将约束条件转化为树的结构，选择哪些节点可攻是必须沿着树根逐级确定。通过递归 DFS，从叶子到根更新每个节点的dp数组，最终在根节点得到最大的宝物总值。

总体来说，树形DP需要系统地构建递归关系，充分利用树的层次结构来实现状态转移。虽然问题复杂度较高，但通过合理的状态设计和递归策略，依然可以得到高效的解决方案。