1
# Runtime: 58 ms (Top 20.54%) | Memory: 13.9 MB (Top 13.32%)
2
class Solution(object):
3
    def numTrees(self, n):
4
        if n == 0 or n == 1:
5
            return 1
6
        # Create 'sol' array of length n+1...
7
        sol = [0] * (n + 1)
8
        # The value of the first index will be 1.
9
        sol[0] = 1
10
        # Run a loop from 1 to n+1...
11
        for i in range(1, n + 1):
12
            # Within the above loop, run a nested loop from 0 to i...
13
            for j in range(i):
14
                # Update the i-th position of the array by adding the multiplication of the respective index...
15
                sol[i] += sol[j] * sol[i - j - 1]
16
        # Return the value of the nth index of the array to get the solution...
17
        return sol[n]