关于树形DP(树形动态规划),该怎么解决

关于树形DP(树形动态规划)
如题，找了两天也没有哪里详细讲这个东西的。。。有哪位高手可以讲解一下。。或者给个链接什么的。。。

树形DP都是二叉树吗？那N叉树怎么办？

在解决这类问题的时候应该怎么建造树呢？如何建立状态转移方程呢？

多谢啦~！

------解决方案--------------------
树形dp不一定要二叉树，主要是注意从叶到根的更新递推关系
上面那个我写个伪代码吧：

C/C++ code

int Max_Tree(int root){
   if( tree[root] 为叶子结点 ){
        return key[root];
    }
    int ans=-INF;
    for (node temp=tree[root]的儿子结点){
        int t1;
        if( (t1=Max_Tree(temp)) > ans ){
            ans=t1;
         }
     }
     return ans;
}

------解决方案--------------------

楼主可以搜索下 泛化背包 
那个就有树形DP的影子
个人觉得那个弄清楚了树形DP也就会了

------解决方案--------------------

泛化背包

------解决方案--------------------
我还以为树形DP，说的是可以转化为阵矩乘相关的DP呢

关于树形DP(树形动态规划),该怎么解决

相关推荐