【文件属性】：
文件名称：转成二叉树后如何DP?-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2021-04-25 05:25:09
动态规划
转成二叉树后如何DP?
状态定义:f[i][j][k]表示以i为根的树上大头吃j个果子的最小难受值之和，k=0表示i的父亲节点由小头吃，k=1则由大头吃。
问题拓展
设左儿子为l, 右儿子为r, Wi是原图上结点i与它父亲的边的难受值。
f[i][j][1] = min{ f[l][k][0]+f[r][j-k][1],
f[l][k-1][1]+f[r][j-k][1]+Wi };
f[i][j][0] = min{ f[l][k-1][1]+f[r][j-k][0],
f[l][k][0]+f[r][j-k][0], (M>2)
f[l][k][0]+f[r][j-k][0]+Wi (M=2) };