Consider a N x N grid with indexes of top left corner as (0, 0). Dyck path is a staircase walk from bottom left, i.e., (N-1, 0) to top right, i.e., (0, N-1) that lies above the diagonal cells (or cells on line from bottom left to top right).
The task is to count the number of Dyck Paths from (N-1, 0) to (0, N-1).
Here are the some of the possible paths for different N.
 
Example 1:
Input:
N = 4
Output:
14 
Explanation:
Refer to the diagram above.
Example 2:
Input:
N = 3
Output:
5
Explanation:
Refer to the diagram above.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function dyckPaths() which takes an Integer N as input and returns the answer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 30

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def dyckPaths(self, N):

        # code here

Solutions:
class Solution:

	def dyckPaths(self, N):
		ans = 1
		for i in range(1, N + 1):
			ans *= N + i
			ans //= i
		return ans // (N + 1)


from math import factorial

class Solution:

	def dyckPaths(self, n):
		return factorial(2 * n) // (factorial(n) * factorial(n + 1))


class Solution:

	def dyckPaths(self, N):
		p = 1
		s = 1
		j = 2
		for i in range(N + 1, 2 * N + 1):
			s = s * i
			p = p * j
			j += 1
			if s % p == 0:
				s = s // p
				p = 1
		return s


class Solution:

	def dyckPaths(self, n):
		dp = [0 for i in range(n + 1)]
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			for j in range(i):
				dp[i] += dp[j] * dp[i - 1 - j]
		return dp[n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.dyckPaths(N))


class Solution:

	def dyckPaths(self, N):
		dp = [0] * (N + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				dp[i] += dp[j] * dp[i - j - 1]
		return dp[N]


class Solution:

	def dyckPaths(self, n):
		f2n = 1
		fn = 1
		for i in range(n + 1, 2 * n + 1):
			f2n *= i
			fn *= i - n
		return f2n // fn // (n + 1)


import math

class Solution:

	def dyckPaths(self, n):
		i = math.factorial(2 * n)
		j = math.factorial(n + 1)
		d = math.factorial(n)
		s = i / (j * d)
		return int(s)


class Solution:

	def dyckPaths(self, N):
		num = 1
		denum = 1
		for i in range(1, N):
			num *= 2 * N - i + 1
			denum *= i + 1
		return num // denum


class Solution:

	def dyckPaths(self, N):
		res = 1
		for i in range(N):
			res *= 2 * N - i
			res //= i + 1
		return res // (N + 1)