C++-এ ইউনিক বাইনারি সার্চ ট্রি গণনা

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

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

n + 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); }