96. Unique Binary Search Trees

Problem

Cho một số nguyên dương n, hãy tính số lượng cấu trúc BST khác nhau có thể tạo ra từ các số nguyên từ 1 đến n, mối số sử dụng đúng 1 lần

Hiểu về BST

Mỗi node của cây có giá trị duy nhất

Mọi giá trị trong cây con bên trái nhỏ hơn giá trị của node gốc

Mọi giá trị trong cây con bên phải lơn hơn giá trị node gốc

Cây con trái và phải cũng phải là BST

Approach

Nhận xét

Với mỗi số i → n, nếu chọn i làm gốc thì

Các số nhỏ hơn i nằm ở cây con bên trái (gồm i - 1 số)

Các số lớn hơn i nằm ở cây con bên phải gồm (n - i số)

Số lượng BST tọa được với n node là tổng các trường hợp chọn từng node làm gốc”

dp = 1 (empty tree)

Dùng mảng dp để lưu số lượng BST ứng với từng số lượng node

Duyệt từ 2 → n, với mỗi số lượng node, thử lần lượt từng node làm gốc, cộng dồn kết quả

Time and space complexity

TC: O(n^2)

SC: O(n)

Solution

typescripttypescript

1function numTrees(n: number): number {
2    const dp: number[] = new Array(n + 1).fill(0);
3    dp[0] = 1;
4    dp[1] = 1;
5    for(let nodes  = 2; nodes <= n; nodes++) {
6	    for(let root = 1; root <= nodes; root++) {
7		    const left = root - 1;
8		    const right = nodes - root;
9		    dp[nodes] += dp[left] * dp[right];
10	    }
11    }
12    
13    return dp[n]
14};

Loading content...