陈益波陈益波香港城市大学香港城市大学2011年年7月月30日日华中科大华中科大2011 ACM暑期集训暑期集训动态规划（三）动态规划（三）状态压缩状态压缩DP 及及 树型树型DP个人简介祖籍：浙江香港城市大学 商学院 09级PhD管理科学专业 OperationResearch.QQ:112997821人人网:陈益波Email:主要内容状态压缩思想状态压缩DP例题讲解树型DP特征树型DP例题讲解总结内容来源树型动态规划和状态压缩动态规划-wangfangbob动态规划的状态方程树形动态规划，状态压缩，结果与参数的互换-李子星树型动态规划的实例分析-李彦亭什么是树型动态规划顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：根叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。叶根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多，下
