Description
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3 Output: 5
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 19
Solution
Python3
class Solution:
def numTrees(self, n: int) -> int:
@cache
def go(n):
if n == 0: return 0
if n == 1: return 1
res = 0
for head in range(n):
res += max(1, go(head)) * max(1, go(n - head - 1))
return res
return go(n)