听ghost讲关于树型动态规划的一点小经验
1.
To 自底向顶 or 自顶向底.This is a question.两种不同的动规方法，应该已经为大家所熟悉了吧？为了for beginers,我就再罗嗦两句：自底向顶，就是先行着眼于处理动态规划中的子问题，再把问题规模不断扩大，最终解决最终问题；自顶向底，就是先行着眼于最终目标，然后探索要达到这个目的需要哪些“次级子问题”，再看每个“次级子问题”需要哪些“次次级子问题”……最终总能找到那些非常好解决的“子问题基元（在打这个词的时候竟然出现了那么HXE（HX+XE）的东西…………）”，然后逐级回溯（就像hitman47在巨菜阶段时辛辛苦苦找那些deb包的依赖关系一样），类似于深度优先搜索的代码印象。两种方法各有千秋，也各有不足。雪知遥神牛喜欢用自顶向底的方法，思考复杂度比较底，但是如果用最易编码的过程（函数）递归来写，每次调用过程就要比自底向顶时数组寻址的时间长一点，浪费了宝贵的N飞秒，所以她一般用数组模拟栈，进行模拟递归（数组模拟栈的方法应该不用再说了吧？），稍稍快了一些；但是这种方法就需要记录每个节点的所有子节点，用（模拟）邻接表储存也需要比自底向顶多开两三个数组，耗费空间。本人(Hitman47)比较喜欢使用自底向顶的动规方法，这种方法比较方便储存（下面一条要说到储存的问题）整个树型关系，比较省空间；不过这种方法的缺点有二：第一，（据雪知遥神牛说）比较不容易想，因为每个问题需要什么往往是一目了然的，但是基元子问题，或者叫边缘值，是什么，从哪里开始处理子问题，子问题与父问题的有向联系究竟怎么实现，都需要爆发一下小宇宙，思索一番，第二：在极限优化方面，由于将要操作的节点所储存的队列（日程表队列）与每个节点的父节点这两个数组储存在内存的不同位置，每完成一个节点就要再转向那个父节点储存单元，这样浪费了时间。
2.
有 planty of 同志s 都曾提到过树型的东东没有很好的储存方法，于是整了一个邻接matrix(膜拜一下matrix67大牛，就用了E文，严重声明，非ZB!)存储所有单向边，结果是既浪费了时间又浪费了空间，其实大可不必这样麻烦。如果你比较习惯自底向上来进行动规，只存储每个节点的父节点就可以，每次处理当前节点后，向它的父节点“汇报”一下自己的结果，当哪个节点的所有子节点都被处理过了（或子节点个数就是0），就把它加进队列，以备未来进行处理；如果你比较习惯自顶向底完成动态规划，就可以用（模拟）邻接表储存各条边，又省时又省电，为共产主义作贡献……扯远了……咳咳……总之，就是空间和时间复杂度都比邻接矩阵要底很多。
3.
以后想起来再说吧……