Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def catalan_number_dp(n):
- # Create a list to store results of subproblems
- catalan = [0] * (n + 1)
- # Base case
- catalan[0] = 1
- # Fill the entries in a bottom-up manner
- for i in range(1, n + 1):
- for j in range(i):
- catalan[i] += catalan[j] * catalan[i - j - 1]
- return catalan[n]
- # Test the function
- for i in range(10):
- print(f"C_{i} = {catalan_number_dp(i)}")
- # Cn valid parenthesis expressions
- # Cn binary trees of n nodes
- # Cn−1 rooted trees of n nodes
- # there are n**(n−2) labeled trees that contain n nodes.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
