题目描述
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.
解题思路
动态规划。找动态规划方程,我们知道当加入第 i 个节点时,他的位置只能为:(左上) -> i -> (左下)。那么这道题目就很简单了,左上和右下的数目都是已知的。
代码
class Solution:
def numTrees(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[1] = 1
if n > 1:
dp[2] = 2
for i in range(3, n + 1):
for j in range(i):
dp[i] += dp[i - 1 - j] * dp[j]
return dp[n]