Unique Binary Search Trees ใน C++

สมมติว่าเรามีจำนวนเต็ม n เราต้องนับต้นไม้ค้นหาไบนารีที่มีโครงสร้างแตกต่างกันทั้งหมดซึ่งเก็บค่าจาก 1 ถึง n ตัวอย่างเช่น หากอินพุตคือ 3 ผลลัพธ์จะเป็น 5 ต้นไม้จะมีดังนี้

ขั้นตอนการแก้ปัญหา

• สร้างอาร์เรย์ขนาด n + 1
• dp[0] := 1
• for i := 1 ถึง n
  • for 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++){ 
                dp[i] += (dp[i - 1 - j] * dp[j]); 
            } 
        } 
        return dp[n]; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << ob.numTrees(4); 
}

อินพุต

4

เอาต์พุต

14