AVL 樹計數 DP 詳解：狀態設計與轉移方程推導

問題同 24687，此為補充說明

DP 狀態

`dp[n][h]` = 節點數 n、高度 h 的 AVL 樹數量。

轉移推導

根節點佔 1 個節點，剩餘 n-1 分配給左右子樹。AVL 條件限制左右子樹高度差 ≤ 1，故只有三種高度組合：

1. (h-1, h-1)
2. (h-1, h-2)
3. (h-2, h-1)

對每種組合，枚舉左子樹節點數 m，右子樹為 n-1-m，累加乘積。

優化提示

• 預計算所有 `dp[n][h]` 至最大 n，查詢 O(1)。
• 利用對稱性：`dp[n][h]` 中 (h-1, h-2) 與 (h-2, h-1) 乘積相同，乘 2 即可。
• 高度上界：`h_max = floor(log_φ(n * sqrt(5) + 0.5))`，φ = (1+√5)/2。

程式碼骨架 (C++)

const int MAXN = 1000;
vector<vector<long long>> dp(MAXN+1, vector<long long>(20, 0));
dp[0][0] = 1;
for (int n = 1; n <= MAXN; n++) {
    for (int h = 1; h < 20; h++) {
        long long ways = 0;
        for (int m = 0; m <= n-1; m++) {
            int r = n-1-m;
            ways += dp[m][h-1] * dp[r][h-1];
            if (h >= 2) ways += 2 * dp[m][h-1] * dp[r][h-2];
        }
        dp[n][h] = ways;
    }
}

結語

同一問題的不同角度解析，幫助理解 DP 狀態設計的靈活性。