C++ 2ms DP solution, easy to understand


  • 0
    J

    class Solution
    {
    public:
    int numTrees(int n) {

        if(n == 0) return 1;
        
        else if(n == 1) return 1;
        
        else if(n == 2) return 2;
        
        vector<int> num(n + 1, 0);
        num[0] = 1;
        num[1] = 1;
        num[2] = 2;
        
        for(int i = 3; i < n + 1; ++i){
            
            for(int j = 1; j <= i; ++j){    //the situation when root is j;
                
                num[i] += (num[j - 1] * num[i - j]);
                
            }
            
        }
        
        return num[n];
        
    }
    

    };

    I created a vector to represent the number of possibilities in range of 1 ~ n.
    If a tree is empty, it is also a tree, so num[0] = 1;

    For every specific n, the root of the tree can be any integer between 1 ~ n, so the total possibilities is the sum of these possibilities combined.

    For a tree with n nodes with root value of j, the number of possibilities of it is the possibilities of left subtree, multiplies the sum of possibilities of the right subtree, which refers to num[j - 1] and num[i - j] respectively.


Log in to reply
 

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