For any n numbers, the number of unique BSTs is sure. E.g. [1, 2, 3] and [2, 3, 4] have the same number of unique BSTs.
On the other hand, the number of unique BSTs for each possible root value v in [1, 2, ..., n] is the number of unique BSTs of [1, 2, ..., v - 1] multiply the number of unique BSTs of [v + 1, v + 2, ..., n].
Thus, the DP formula of this problem could be:
dp(0) = 1 dp(n) = sum([dp(i) * dp(n - i - 1) for i in range(0, n)])
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
for length in range(1, n + 1):
for i in range(0, length):
dp[length] += dp[i] * dp[length - i - 1]
return dp[n]
# TODO: Add position save for vim.
def main():
cases = [0, 1, 2, 3]
for case in cases:
print(case, Solution().numTrees(case))
if __name__ == "__main__":
main()