C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++のユニークな二分探索木

整数nがあるとすると、1からnまでの値を格納する構造的に一意のすべての二分探索木を数える必要があります。したがって、入力が3の場合、ツリーは–

になるため、出力は5になります。

C++のユニークな二分探索木

これを解決するには、次の手順に従います–

  • サイズn+1の配列を1つ作成します
  • dp [0]：=1
  • for i：=1からn
    • for j：=0 to i – 1
      • dp [i]：=dp [i] +（dp [i – 1 – j] * dp [j]）
  • return dp [n]
例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numTrees(int n) {
      vector <int> dp(n+1);
      dp[0] = 1;
      for(int i =1;i<=n;i++){
         for(int j = 0;j<i;j++){
            //cout << j << " " << i-1-j << " " << j << endl;
            dp[i] += (dp[i-1-j] * dp[j]);
         }
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout << ob.numTrees(4);
}
入力 
4

出力

14

  1. C ++プログラムでの二分探索？

    二分探索は、半区間探索、対数探索、または二分探索とも呼ばれ、ソートされた配列内のターゲット値の位置を見つける検索アルゴリズムです。二分探索は、ターゲット値を配列の中央の要素と比較します。それらが等しくない場合、ターゲットが存在できない半分が削除され、残りの半分で検索が続行され、再び中央の要素がターゲット値と比較され、ターゲット値が見つかるまでこれが繰り返されます。残りの半分が空の状態で検索が終了した場合、ターゲットは配列に含まれていません。アイデアは単純ですが、バイナリ検索を正しく実装するには、特に配列の値が範囲内の整数のすべてではない場合、終了条件と中間点の計算に関する微妙な点に注意する必要

  2. C＃での二分探索

    バイナリ検索はソートされた配列で機能します。値は配列の中央の要素と比較されます。同等性が見つからない場合は、値が存在しない半分の部分が削除されます。同様に、残りの半分の部分が検索されます。 これが配列のmid要素です。 62を見つける必要があるとしましょう。そうすると、左側の部分が削除され、右側の部分が検索されます- これらは二分探索の複雑さです- 最悪の場合のパフォーマンス O（log n） ベストケースのパフォーマンス O（1） 平均パフォーマンス O（log n） 最悪の場合のスペースの複雑さ O（1） 例 二分