C++ এ অনন্য বাইনারি অনুসন্ধান গাছ

ধরুন আমাদের একটি পূর্ণসংখ্যা n আছে, আমাদেরকে 1 থেকে n পর্যন্ত মান সঞ্চয় করে এমন সমস্ত কাঠামোগতভাবে অনন্য বাইনারি সার্চ ট্রি গণনা করতে হবে। সুতরাং যদি ইনপুট 3 হয়, তাহলে আউটপুট 5 হবে, যেমন গাছগুলি হবে –

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব –

ন + 1 আকারের একটি অ্যারে তৈরি করুন
dp[0] :=1
এর জন্য i :=1 থেকে n
- j এর জন্য :=0 থেকে i – 1
  - dp[i] :=dp[i] + (dp[i – 1 – j] * dp[j])
রিটার্ন 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);
}

ইনপুট

৷