0ms c++ solution using DP


  • 0
    L

    My basic thinking is pick up one number k as root node from 1 to n, and using [0, k-1] and [k+1, n] to build its left and right child tree respectively. using [0, k-1] because 0 represents for null child tree, but also a situation to be considered. If [0, k-1] has m unique BST, and [k+1, n] has n unique BST, then under this circumstance of number k as root, we have m*n unique BST.

    int numTrees(int n) {
        vector<int> trees(n+1, 1);
        for(int i = 2; i <= n; i++)
        {
            int j = 0, k = i-1;
            for(; j < k; j++, k--)
                trees[i] += (trees[j] * trees[k] * 2);
            if(j == k)
                trees[i] += (trees[j] * trees[k]);
        }
        return trees[n];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.