Pernyataan masalah
Diberikan bilangan bulat n, kembalikan jumlah BST yang unik secara struktural (pohon pencarian biner) yang memiliki tepat n simpul dengan nilai unik dari 1 hingga n .
Pernyataan masalah diambil dari: https://leetcode.com/problems/unique-binary-search-trees.
Contoh 1:
Input: n = 3
Output: 5Contoh 2:
Input: n = 1
Output: 1Kendala:
- 1 <= n <= 19Penjelasan
Solusi kekerasan
Pendekatan brute force adalah menghasilkan semua BST yang mungkin dan menghitungnya. Pendekatan ini akan memakan banyak waktu ketika kita meningkatkan n.
Pemrograman Dinamis
Dengan Pemrograman Dinamis, kami akan mengurangi cakupan pembuatan BST dan menggunakan konsep matematika untuk mendapatkan hasil yang diperlukan.
Mari kita ambil contoh dimana n adalah 5. Jika simpul 2 adalah akar, maka subpohon kiri akan berisi 1 dan subpohon kanan akan berisi 3, 4, dan 5. Banyaknya kemungkinan kombinasi pada subpohon kiri adalah 1, dan pada subpohon kanan adalah 5. Kita mengalikan 1 dan 5. Demikian pula, jika 3 adalah simpul akar, maka banyaknya kemungkinan kombinasi pada subpohon kiri subpohonnya adalah 2, dan jumlah kombinasi pada subpohon kanannya adalah 2. Jadi total BST ketika simpul akar 3 adalah 2*2 = 4. Kami menjumlahkan semua kombinasi ini untuk setiap node 1 hingga n dan mengembalikan hasil yang diperlukan.
Cuplikan C++ dari pendekatan di atas adalah sebagai berikut:
int numberOfBST(int n) {
int dp[n + 1];
fill_n(dp, n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] = dp[i] + (dp[i - j] * dp[j - 1]);
}
}
return dp[n];
}Kompleksitas waktu dari pendekatan di atas adalah O(N²) dan kompleksitas ruang adalah O(N).
Nomor Catalan
Bilangan Catalan, dalam matematika kombinatorial, adalah barisan bilangan asli yang muncul dalam berbagai soal penghitungan, sering kali melibatkan objek yang ditentukan secara rekursif.
Dilambangkan dengan Cn dan rumus menghitungnya adalah (2n)! / ((n + 1)! * n!).
Mari kita periksa algoritme untuk melihat bagaimana kita dapat menggunakan rumus ini.
// numTrees function
- return catalan(2*n, n)
// catalan function
catalan(n , k)
- set result = 1
- if k > n - k
- k = n - k
- for i = 0; i < k; i++
- result *= (n - i)
- result /= (i + 1)
- return result/(k + 1)Kompleksitas waktu dari pendekatan ini adalah O(N), dan kompleksitas ruang adalah O(1). Mari kita periksa solusi kami di C++, Golang, dan Javascript.
solusi C++
class Solution {
public:
long long catalan(int n, int k) {
long long result = 1;
if(k > n - k) {
k = n - k;
}
for(int i = 0; i < k; i++) {
result *= (n - i);
result /= (i + 1);
}
return result/(k + 1);
}
int numTrees(int n) {
long long result = catalan(2*n , n );
return (int) result ;
}
};Solusi Golang
func catalan(n, k int) int {
result := 1
if k > n - k {
k = n - k
}
for i := 0; i < k; i++ {
result *= (n - i)
result /= (i + 1)
}
return result/(k + 1)
}
func numTrees(n int) int {
return catalan(2*n , n )
}Solusi Javascript
var catalan = function(n, k) {
let result = 1;
if(k > n - k) {
k = n - k;
}
for(let i = 0; i < k; i++) {
result *= (n - i);
result /= (i + 1);
}
return result/(k + 1);
}
var numTrees = function(n) {
return catalan(2*n, n);
};Mari kita uji algoritme kita untuk melihat cara kerja solusinya.
Input n = 4
Step 1: result = catalan(2*n , n )
= catalan(2*4, 4)
= catalan(8, 4)
// catalan function
Step 2: result = 1
n = 8, k = 4
Step 3: if k > n - k
4 > 8 - 4
4 > 4
false
Step 4: loop for i = 0; i < k
0 < 4
true
result *= (n - i)
= result * (n - i)
= 1 * (8 - 0)
= 8
result /= (i + 1)
= result / (i + 1)
= 8 / (0 + 1)
= 8
i++
i = 1
Step 5: loop for i < k
1 < 4
true
result *= (n - i)
= result * (n - i)
= 8 * (8 - 1)
= 8 * 7
= 56
result /= (i + 1)
= result / (i + 1)
= 56 / (1 + 1)
= 56 / 2
= 28
i++
i = 2
Step 6: loop for i < k
2 < 4
true
result *= (n - i)
= result * (n - i)
= 28 * (8 - 2)
= 28 * 6
= 168
result /= (i + 1)
= result / (i + 1)
= 168 / (2 + 1)
= 168 / 3
= 56
i++
i = 3
Step 7: loop for i < k
3 < 4
true
result *= (n - i)
= result * (n - i)
= 56 * (8 - 3)
= 56 * 5
= 280
result /= (i + 1)
= result / (i + 1)
= 280 / (3 + 1)
= 280 / 4
= 70
i++
i = 4
Step 8: loop for i < k
4 < 4
false
Step 9: return result/(k + 1)
70/(4 + 1)
70/5
14
So we return the answer as 14.Awalnya diterbitkan di https://alkeshghorpade.me.\
