異なる二叉探索ツリー--dp解決

0x01.に質問
整数nを与えて、1...nをノードとして構成する二叉探索ツリーを求めるのは何種類ありますか?入力例:3出力例:5解釈:シーケンス1,2,3に対して,全部で5種類の異なる二叉探索ツリーを構成できる

C++     ：     int numTrees(int n) 

0x02.簡単な分析
この問題は,長さnの秩序配列を与え,二叉探索ツリーを構成する可能性のある組合せ数を求めることに相当する.
例を見てみましょう

シーケンス1,2,3,4,5,6,7,8,9に対して、全部で何種類の二叉ソートツリーを構成することができますか?

二叉ソートツリーを構成するには、まずルートを選択します.ルートはいくらですか?答えはシーケンス内の任意の値です.これは秩序化されたシーケンスなので、どのように選択しても左のものはそれより小さい(または左のツリーがない)、右のものはそれより大きい(または右のツリーがない)ので、ルートノードの選択は任意です.
ルートノードを選択した後、左右のサブツリーはどのように選択しますか?実は左右のサブツリーもいくつかのサブツリーの根と見なすことができて、選択方法は同じで、だから、これは繰り返しの過程です.
反復関係をどのように見つけますか?9までと仮定すると、前の組合せ数はすべて算出されている.今は5を根として選んでいますが、その可能性は * で、左の木の可能性はどのくらいですか?1,2,3,4で作られた木の可能性ですが、右の木は?6,7,8,9で発生した木の可能性ですが、左右の木をもう一度反復するのでしょうか.実は必要ありません.1つの秩序あるシーケンスからなる種数は、そのシーケンスの個数だけに関係しているので、他のものとは関係ありません.つまり、左側の4つの要素は、その木がdp[4]に等しく、右側がdp[4]に等しく、動的計画の思想に基づいて、私たちは前の計算を仮定して、これらはすべて既知の条件です.
したがって,状態遷移方程式を得ることができる.

for(int j=1;j<=i;j++){
    dp[i]+=dp[i-1]*dp[i-j];
}

0x03.解決コード–動的計画

int numTrees(int n) {
    vector<int>dp(n+1,0);
    if(n<=1) return 1;
    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];
}

ATFWUS --Writing By 2020–03–26