想好久= =,給定一個 前序遍歷 的順序,求出有幾棵樹符合此結果。

看了題解才會, dp[i][j] 表示 結點i 到 結點j 所能構成的樹總數。

設dp[i][j]表示從i個點到j個點所能構成的樹的總數。

通過枚舉回退點來重疊計算,以回退點為根(起點,回退點,終點必須相等),dp[i+1][k-1]*f[k][j]。

dp[i+1][k-1],表示從第i+1個點到第k-1個點不會回退到根k的樹。

dp[k][j]的是會回到根的,避免了相對結構數的重複計算
......解法轉貼自題解網站

所以不附code了。

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()