Hi friends!
Welcome to GeeksforGeeks.
Today we will learn how to write program to calculate the nth catalan number.
Catalan Numbers are a sequence of natural numbers that occur in some interesting counting
problems like Count the number of expressions containing
n pairs of parentheses which are correctly matched.
Count the number of possible Binary Search Trees with n Keys.
Count the number of full binary trees with n+1 leaves.
Triangulation of (n+2)gon.
Handshake Problem.
The beauty of catalan numbers is it occurs in various counting problems.
We will look at two interesting problems and different approaches to solve it.
Problem 1: Count the number of possible Binary Search Trees with n Keys.
Case 1 is to find number of possible binary search trees where node is 1 and key is 5.
There can be only one solution where 5 is selected as a root node.
Catalan is an array that stores nth catalan value.
So, catalan of 1 is 1.
Case 2 is to find number of possible binary search trees where nodes are 2 and keys are
5 and 6.
There are 2 possible binary search trees.
Either 5 is selected as a root node or 6 is selected as a root node.
So, catalan of 2 is 2.
Case 3 is to find number of possible binary search trees where nodes are 3 and keys are
5, 6 and 7.
There are 3 choices at first view.
First, if 5 is selected as a root node then either 6 or 7 can be used as next node.
Hence, possible binary search trees are 2.
Second, if 6 is selected as a root node then possible binary search tree is 1.
Third, if 7 is selected as a root node then either 5 or 6 can be used as next node.
Hence, possible binary search trees are 2.
Total value becomes 5.
So catalan of 3 is 5.
The logic behind drawing possible binary search trees is to choose one node at a time as a
root node.
If 5 is root, nodes at left side is 0 and nodes at right side are 2.
So catalan of 0 into catalan of 2 is 2.
If 6 is root, nodes at left side is 1 and nodes at right side is 1.
So catalan of 1 into catalan of 1 is 1.
If 7 is root, nodes at left side are 2 and nodes at right side is 0.
So catalan of 2 into catalan of 0 is 2.
We get catalan of 3 as 5.
Case 4 is to find number of possible binary search trees where nodes are 4 and keys are
5, 6, 7 and 8.
Case 4 can be directly solved using this simple logic.
There is no hassle of drawing possible binary search trees.
Catalan of 4 is calculated by choosing 4 different values of root node.
When root is 5 plus when root node is 6 plus when root node is 7 plus when root node is
8.
So catalan of 4 becomes 14.
This code is the implementation of recursive formula we discussed.
We declare the base case as catalan of number less than or equal to 1 is 1.
Else for each ith number, recursively keep adding the value of catalan of i into catalan
of n-i-1 to res variable.
At the end we return res value.
We should notice here that catalan of i is selected from first i numbers and catalan
of n-i-1 is selected from remaining numbers.
To consider all the subsets of items, there can be two cases for each item: The item is
a root node.
The item is not a root node.
We can observe that recursive implementation does a lot of repeated work.
It computes catalan of 3 twice.
Since subproblems are evaluated again, this problem has overlapping subproblems property.
So recomputation of same subproblem can be avoided by constructing array catalan in bottom
up manner.
We can use dynamic programming for this.
This code is a dynamic programming based implementation to find nth catalan number.
We have declared catalan as an array to store results of subproblems.
Catalan of 0 and catalan of 1 is initialised to 1.
For rest of the numbers, we compute catalan by selecting each i till i is less than or
equal to n using this recursive formula where jth node is selected as a root node in each
iteration.
Catalan of j is selected from first j numbers and catalan of i-j-1 is selected from remaining
numbers.
At last return the value of catalan of n.
Thanks for watching.
For any queries or doubt, please comment below.
Không có nhận xét nào:
Đăng nhận xét