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