Posted on 2007-06-06 17:40
ZelluX 阅读(612)
评论(0) 编辑 收藏 所属分类:
Algorithm
发信人: DragonZhao (狂抽猛干·抽时间干事业), 信区: Algorithm
标 题: 一个问题
发信站: 日月光华 (2007年05月21日01:26:41 星期一), 站内信件
已知存在二叉树节点结构node{node* left; node* right};，现在给出树的根节点node*
root与自然数int m，要求搜索此树中节点数为m的子树的数量。如何做效率最高？
发信人: wshxzt (WKFB2008), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年05月21日01:28:34 星期一), 站内信件
树的动态规划
发信人: lovebei (0124·皮皮和卡卡), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年06月06日13:36:43 星期三), 站内信件
以i为根节点 节点数为j的子树个数
p[i][j]=∑{p[left(i)][k]*p[right(i)][j-k-1]} 0<=k<=j-1
发信人: Jeru (柠檬树), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年06月06日13:59:36 星期三), 站内信件
没错的。不过硬要说是动态规划也没错，这个概念太宽泛了。
发信人: jesseg (Jesse : 我是花朵，祖国的希望!), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年06月06日16:12:04 星期三)
其实这不至于算dp啦，dp的好处没发挥出来，呵呵，树状的搜索不用dp的，要图状的时候
dp才能省计算。