0ms c++ solution using DP

  • 0

    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.