使用動態程序的加泰羅尼亞號碼

Question

我正在計算具有n個節點的二叉搜索樹的數量，我發現它是加泰羅尼亞號碼。

現在，使用DP，這是我的嘗試。

create arr[n+1]; 
arr[0]=1; 
arr[1]=1; 
for(i=2;i<n+1;i++) 
    arr[i]=0; 
    for(j=1;j<i;j++) 
    arr[i]+=arr[i-j]*arr[j]; 

//arr[n] gives the answer? 

這是正確的方法嗎？

它可以更好嗎？

Answer 1

我不認爲你的代碼有效。你是指數字從1到n的唯一二進制搜索樹的數量？

對於n = 3，編號應爲5。但是你的代碼給了我結果2。

1   3  3  2  1 
\  / / /\  \ 
    3  2  1  1 3  2 
/ /  \     \ 
2  1   2     3 

這裏是我的解決方案：

int numTrees(int n) { 
    int dp[n+1]; 
    memset(dp, 0, sizeof(dp)); 
    dp[0] = 1; 
    dp[1] = 1; 
    for (int i = 2; i <= n; ++i) 
     for (int j = 1; j <= i; j++) 
      dp[i] += dp[j-1] * dp[i-j]; 
    return dp[n]; 
} 

對於加泰羅尼亞號碼，P(3) = P(1)P(2) + P(2)P(1)。

但是在這個問題上，P(3) = P(0)P(2) + P(1)P(1) + P(2)P(0)。

所以，我想這不是加泰羅尼亞數字。 希望這可以幫助你。