ต้นไม้การค้นหาไบนารีที่ไม่ซ้ำกันใน 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