Posted on 2007-06-06 17:40
ZelluX 閱讀(622)
評論(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才能省計算。