February 24, 2019

96. Unique Binary Search Trees

动态规划问题。

Java:

class Solution {
    public int numTrees(int n) {
        int[] numTrees = new int[n + 1];
        numTrees[0] = 1;
        numTrees[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                numTrees[i] += numTrees[j - 1] * numTrees[i - j];
            }
        }
        return numTrees[n];
    }
}

Python:

class Solution:
    def numTrees(self, n: int) -> int:
        nums = [0] * (n + 1)
        nums[0], nums[1] = 1, 1
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                nums[i] += nums[j - 1] * nums[i - j]
        return nums[n]