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

इनपुट

4

आउटपुट

14