C++ . में अद्वितीय बाइनरी सर्च ट्री

मान लीजिए कि हमारे पास एक पूर्णांक n है, हमें सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री को गिनना होगा जो 1 से n तक के मानों को संग्रहीत करते हैं। तो अगर इनपुट 3 है, तो आउटपुट 5 होगा, जैसे पेड़ होंगे -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n + 1 आकार की एक सरणी बनाएं
• dp[0] :=1
• i के लिए:=1 से n
  • जे के लिए:=0 से i - 1
    • dp[i] :=dp[i] + (dp[i – 1 – j] * dp[j])
• रिटर्न डीपी[एन]

उदाहरण(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