Problem Statement
Which of the following problems uses Catalan numbers?
Explanation
Catalan numbers represent the number of structurally unique binary search trees with n nodes. The nth Catalan number is C of n equals 1 divided by n plus 1 times 2n choose n, which equals 2n factorial divided by n plus 1 factorial times n factorial.
Catalan numbers appear in many combinatorial problems including counting the number of valid parentheses expressions with n pairs, the number of ways to triangulate a polygon with n plus 2 sides, the number of paths in a grid that do not cross the diagonal, and the number of ways to multiply n plus 1 matrices. The formula can be computed using dynamic programming with C of n equals sum from i equals 0 to n minus 1 of C of i times C of n minus 1 minus i.
Code Solution
SolutionRead Only
// Number of unique BSTs with n nodes
int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1; // Empty tree
dp[1] = 1; // One node
// Catalan number formula
for (int nodes = 2; nodes <= n; nodes++) {
for (int root = 1; root <= nodes; root++) {
// Left subtree: root-1 nodes
// Right subtree: nodes-root nodes
dp[nodes] += dp[root-1] * dp[nodes-root];
}
}
return dp[n];
}
// Examples:
// n=1: 1 BST
// n=2: 2 BSTs
// n=3: 5 BSTs
// 1 1 2 3 3
// \ \ / \ / /
// 3 2 1 3 2 1
// / \ \ \
// 2 3 1 2
// Time: O(n^2), Space: O(n)