Add nth Catalan number (fixes TheAlgorithms#2402) (TheAlgorithms#2518)

amritesh19 · web-flow · commit 972f134408bf · 2021-10-11T14:03:40.000+03:00
diff --git a/DynamicProgramming/CatalanNumber.java b/DynamicProgramming/CatalanNumber.java
@@ -0,0 +1,60 @@
+package DynamicProgramming;
+
+/**
+ * This file contains an implementation of finding the nth CATALAN NUMBER using dynamic programming
+ * Wikipedia: https://en.wikipedia.org/wiki/Catalan_number
+ * 
+ * Time Complexity: O(n^2)
+ * Space Complexity: O(n)
+ * 
+ * @author AMRITESH ANAND (https://github.com/amritesh19) 
+ */
+
+import java.util.Scanner;
+
+public class CatalanNumber {
+
+  /**
+   * This method finds the nth Catalan number
+   *
+   * @param n input n which determines the nth Catalan number
+   *          n should be less than equal to 50 as 50th Catalan number is 6,533,841,209,031,609,592
+   *          for n > 50, BigInteger class should be used instead long   
+   * 
+   * @return catalanArray[n] the nth Catalan number
+   */
+    static long findNthCatalan(int n){
+
+        // Array to store the results of subproblems i.e Catalan numbers from [1...n-1]
+        long catalanArray[] = new long[n + 1];
+
+        // Initialising C₀ = 1 and C₁ = 1 
+        catalanArray[0] = 1;
+        catalanArray[1] = 1;
+
+        /**
+         * The Catalan numbers satisfy the recurrence relation
+         * C₀=1 and Cn = Σ (Ci * Cn-1-i),  i = 0 to n-1 , n > 0 
+         */ 
+        for(int i = 2; i <= n; i++){
+            catalanArray[i] = 0;
+            for(int j = 0; j < i; j++){
+                catalanArray[i] += catalanArray[j] * catalanArray[i - j - 1];
+            }
+        }
+
+        return catalanArray[n];
+    }
+
+    // Main method
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+
+        System.out.println("Enter the number n to find nth Catalan number (n <= 50)");
+        int n = sc.nextInt();
+        System.out.println(n + "th Catalan number is " + findNthCatalan(n));
+        
+        sc.close();
+    }
+}
+
