深度為n的滿二叉樹中選擇k個點，不能有直系親屬關係，共有多少種選法？

01-07

有沒有解析解？

設在 n 層的滿二叉樹中選 k 個點（無直系親屬關係）有 $f[n,k]$ 種選法。

初始條件： $f[1,0] = f[1,1] = 1$

遞推式： $f[n,k] = left( sum_{i=0}^k f[n-1,i] f[n-1,k-i] ight) + mathbf{1}_{k=1}$

解釋：除非 k=1，否則根結點肯定不能選。於是要選 k 個點，就相當於在兩棵子樹中分別選 i 和 k-i 個點。當 k=1 的時候，可以選根結點，於是額外加上 1。

上面的遞推式可以用母函數簡潔地表達。設多項式 $F_n(x)$ 的 k 次項係數為 $f[n,k]$ ，則有：

$F_1(x) = x+1$

$F_n(x) = [F_{n-1}(x)]^2 + x$

通項我不會求……

類似這個題么？

POJ 2342.Anniversary party

樹形dp

dp[i][0] += dp[j][1]

dp[i][1] += max(dp[j][1],dp[j][0])

把題目的最大值改成計數之類的方法吧，提供個思路，僅供參考

廣告下自己博客的題解

http://www.oyohyee.com/post/POJ/2342.html

令f[i][j][k]為深度為i的滿二叉樹取j個其中有k個在最後一層的取法

然後暴力轉移一下

推那個狀態轉移公式蠻難寫出來

反正程序寫出來應該蠻清晰的