Leetcode 96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

This problem is slightly different from last one. It does not require trees, but require numbers. Actually this is much easier, and we can use DP. This number is Catalan number.

Usually, when specific result is required, we use DFS; when the problem just wants a number, we consider DP.

Solution:

# T:O(n^2) S:O(n)
class Solution:
    # @return an integer
    def numTrees(self, n):
        dp = [1, 1, 2]
        if n <= 2:
            return dp[n]
        else:
            dp += [0 for i in range(n-2)]
            for i in range(3, n + 1):
                for j in range(1, i+1):
                    dp[i] += dp[j-1] * dp[i-j]
            return dp[n]

Run Time: 60 ms