Problem statement

https://binarysearch.com/problems/Number-of-Unique-Binary-Search-Trees/

Solution

Equal to Leetcode 0096. Unique Binary Search Trees, but here we need to compute given module.

Complexity

Here is O(n^2) time complexity solution.

Code

class Solution:
    def solve(self, n):
        if n == 0: return 1
        dp = [0]*(n+1)
        dp[0], dp[1] = 1, 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
            dp[i] %= (10**9 + 7)
        return dp[n]

Remark

It is possible to make it O(n) time as well.