DP Solution: O(N^2) time, O(N) space. is there a better way?


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

  • 2
    V

    Number of unique binary search trees for the given integer n is indeed the CATALAN NUMBER

    class Solution {
    public:
        int numTrees(int n) {
            long int  result = 1;
            for(int i = 1; i <= n; ++ i)
                result  = result * 2 * (2 * i - 1) / (i + 1);
            return result;
        }
    };

  • 0
    P

    Can you explain a bit, specifically this - result * 2 * (2 * i - 1) / (i + 1);


Log in to reply
 

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