title
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Constraints:
1 <= n <= 19
solution
class Solution:
def numTrees(self, n: int) -> int:
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][i] = 1
for l in range(1, n):
for i in range(1, n - l + 1):
j = i + l
for k in range(i, j + 1):
dp[i][j] += (dp[i][k-1] if k-1>=i else 1) * (dp[k+1][j] if k+1<=j else 1)
return dp[1][n]