デカルト固有のBSTの数を求めるデカルト積を使った直観

Question

私はLeetCode質問を解決しています。質問です：1...nから値を格納する構造的にユニークな分探索木を生成することができますどのように多くのn考える

、？

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

最大upvoted溶液はDPを利用して、次の再帰式：

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 

G(n)次のようにために、例えば、n=3ため、5ユニーク分探索木の合計を生成することができますnに対して生成できる一意のBSTの数を表します。コードは次のとおりです。

class Solution { 
public: 
    int numTrees(int n) { 
     vector<int> G(n+1); 
     G[0]=G[1]=1; 

     for(int i=2; i<=n; i++) 
      for(int j=1; j<=i; j++) 
       G[i]+=G[j-1]*G[i-j]; 

     return G[n]; 
    } 
}; 

を、多かれ少なかれ、私は何が起こっているかを理解しないが、我々はより直感的である直積（代わりに、単純な加算を取る理由は、私は理解していませんでした）。私の理解あたりとして：

G[i] += G[j-1] * G[i-j]; 

は、代わりに次のようになります。

G[i] += G[j-1] + G[i-j]; //replaced '*' with a '+' 

、私は現在のルートとしてiで可能なユニークな分探索木の数が合計（あるべきだと思うので、これはそうでしょうか？ ）の左および右のサブツリーのBSTの数を示します。私はいくつかの例を試しましたが、どういうわけか数字は元の解答（*）で魔法のように掛け合わされ、最終的な答えはG[n]に現れます。

合計の代わりにデカルト積を使用するための直観的な説明を提供してもらえますか？

注：元の質問はhereで解決はhereです。また、元のコードはJavaで書かれていますが、私が上で書いたC++のバリエーションを投稿しています。

Answer 1

あなたは数学的誘導によって行くことができ、結果を得るためにそれをサブ問題に適用することができます。あるいは単に小さな値をチェックして、より高い値にするだけです。例えば

： -

No of nodes  BST representation 

1 --> [1] 

2 --> [2] [1] 
     / \ 
     [1] [2] 

3 --> [1] 
      \ 
      [2] 
      \ 
      [3] 

     [2] 
     /\ 
     [1] [3] 

      [3] 
     /
     [2] 
    /
     [1] 
4 --> 
     [1] 
    / \ 
    NUM{} NUM of keys with 3 val NUM{2,3,4} 

     [2] 
    /\ 
    NUM{1} NUM{3,4} 

     [3] 
    /\ 
    NUM{1,2} NUM{4} 

      [4] 
     / \ 
    NUM{1,2,3} NUM{} 

あなたは私たちが単に木の各グループに左と右のサブツリーを可能な方法の数を乗算しなければならないことを明確に理解することができます第四ケースから。与えられた数の値に対して、それらを追加する必要があります。だから、デカルト製品が使われているのです。

本製品は、基本的に真実が持つ可能性のあるすべての可能な順序を提供します。例えば ：

ここ

G[i] += G[j-1] * G[i-j];j-1ノードが左側にあり、右側のサブツリーにi-jノード（我々は、一般性を失うことなく をとることができます）。今度は G[j-1]の方法で左のサブツリーを配置することができ、同様に の右のサブツリーについては、G[i-j]の方法で並べ替えることができます。今、この左とリグのサブツリーを持っている元のツリーをどのように多くの方法で整理できますか ？それは になります。左サブツリーと右サブツリーの各組み合わせは、 に一意のツリー表現を与えるためです。

G[0]=1は、私たちがここでのやり方に従うからです。また、価値のない取り決めの数も同様です。それで1とみなされます。