c++ DP Solution


  • 0

    numTrees(n) += numTrees(i)*numTrees(n-i-1); // i in [0, n - 1]

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

Log in to reply
 

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