USACO Cow Pedigrees

給定N和K，問有多少棵高度為K、N個頂點的二叉樹。對二叉樹的要求是除葉子外所有頂點必須有兩個子節點。

明明是很簡單的動態規劃，卻搞了我很多時間…

定義目標函數 F[N][K] 即題目要求數。

觀察﹕
(1) F[N][K]必須依賴 F[i][K-1]，使得二叉樹數符合要求。
(2) 必須分配單數子節點予任意子樹，否則必得無乎合要求的二叉樹。
(3) 得出轉移方程為 F[i][K-1] * F[N-1-i][j] * 2 的總和，當中 j < K-1。
(4) 另需加上F[i][K-1] * F[N-i-1][K-1]，因為交換子樹視同相等。
(5) 合法狀態必須符合 2*K < N + 2，因為一棵符合要求的子樹至少是Left Completed，必然有2 * K - 1點，否則無法構建二叉樹。

沒有留意(5)便會造成很多無謂的錯誤。