C语言中树型动态规划算法思想如何深入剖析？

本文共计4011个文字，预计阅读时间需要17分钟。

1. 前言：什么是树型动态规划？概念中有2个子概念：一是动态规划概念，二是动态规划概念。动态规划可以简单理解为通过对已经计算出的子问题的状态值进行修改（基于子问题的状态值找到当前子）。

1. 前言

什么是树型动态规划？

概念中有 2 个子概念：

• 一个是动态规划概念。动态规划可以简单理解为通过对已经计算出来的子问题的状态值进行修改(基于子问题的状态值找到当前子问题的最优值)而得到当前子问题的状态值。

Tips： 本文侧重于动态规划在树型结构中的应用，更多关于动态规划的基础理论和常规知识，可以翻阅相关资料。

• 树指树数据结构。树型动态规划算法指在树逻辑结构之上提供的动态规划思想。

动态规划最重要环节查找到子问题间发生变化的状态量以及状态转移表达式。树型动态规划的状态转移过程一般都是由子树向根结点转移，这也符合动态规划的由底向上的逻辑思想。

本文通过讲解几个经典的树型动态规划案例，揭开其神秘面纱。

2. 经典案例

2.1 没有上司的舞会

没有上司的舞会是树型动态规划最经典的案例。下文将剖析此案例的细节，从而深度理解树型动态规划的逻辑流程。

问题描述：

某公司有 n 个职员，编号为 1∼N。公司吗，必然存上、下级关系。员工之间的关系从逻辑结构而言，就是典型的树结构。

在树结构中，父结点是子结点的直接上司。