Unique Binary Search Trees

Intuition

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)])

Solution


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()