Số cây tìm kiếm nhị phân duy nhất trong C++

Cho một số nguyên n, hãy đếm tất cả các cây tìm kiếm nhị phân (BST) cấu trúc duy nhất lưu trữ giá trị từ 1 đến n. Ví dụ, nếu n = 3, đầu ra là 5, như hình minh họa:

Đây là bài toán Catalan numbers. Giải pháp dùng quy hoạch động:

• Tạo mảng dp kích thước n + 1
• dp[0] := 1
• Với i từ 1 đến n:
  • Với j từ 0 đến i-1:
    • dp[i] := dp[i] + (dp[i-1-j] * dp[j])
• Trả về dp[n]

Ví dụ (C++):

Xem triển khai sau để hiểu rõ hơn:

#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); 
    return 0;
}

Đầu vào

4

Đầu ra

14