Java Program for nth Catalan Number using Dynamic Programming
We can observe that the above recursive implementation does a lot of repeated work. Since there are overlapping subproblems, we can use dynamic programming for this.
Below is the implementation of the above idea:
- Create an array catalan[] for storing ith Catalan number.
- Initialize, catalan[0] and catalan[1] = 1
- Loop through i = 2 to the given Catalan number n.
- Loop through j = 0 to j < i and Keep adding value of catalan[j] * catalan[i – j – 1] into catalan[i].
- Finally, return catalan[n]
Below is the implementation of the above approach:
Java
import java.io.*;class GFG { // A dynamic programming based function to find nth // Catalan number static int catalanDP(int n) { // Table to store results of subproblems int catalan[] = new int[n + 2]; // Initialize first two values in table catalan[0] = 1; catalan[1] = 1; // Fill entries in catalan[] // using recursive formula for (int i = 2; i <= n; i++) { catalan[i] = 0; for (int j = 0; j < i; j++) { catalan[i] += catalan[j] * catalan[i - j - 1]; } } // Return last entry return catalan[n]; } // Driver code public static void main(String[] args) { for (int i = 0; i < 10; i++) { System.out.print(catalanDP(i) + " "); } }}// This code contributed by Rajput-Ji |
Output
1 1 2 5 14 42 132 429 1430 4862
Time Complexity: O(n2)
Auxiliary Space: O(n)
Java Program for nth Catalan Number
Catalan numbers are defined as a mathematical sequence that consists of positive integers, which can be used to find the number of possibilities of various combinations.
The nth term in the sequence denoted Cn, is found in the following formula:
The first few Catalan numbers for n = 0, 1, 2, 3, … are : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
Catalan numbers occur in many interesting counting problems like the following.
- Count the number of expressions containing n pairs of parentheses that are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
- Count the number of possible Binary Search Trees with n keys (See this)
- Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
- Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.
Examples:
Input: n = 6
Output: 132Input: n = 8
Output: 1430