My DP java solution


  • 0
    M
    public int numTrees(int n) {
        if(n<=2){
            return n;
        }
        int[] num=new int[n+1];
        num[0]=0;
        num[1]=1;
        num[2]=2;
        for(int i=3;i<n+1;i++){
            num[i]=num[i-1]*2;
            for(int j=1;j<=i-1-1;j++){
                num[i]+=num[j]*num[i-1-j];
            }
        }
        return num[n];
    }
    

    Eg, if n=4, then we need to count num[3] * 2, because for each of the possible binary tree of n=3, we can insert 4 in 2 positions. Then we also can insert 4 "into" tree-3, i.e. break 123 into two groups
    [1] 4 [23] or [12] 4 [3] (please imagine the tree structure, it doesn't violate the binary property, but just divide 123 apart into 2 parts)
    for the first condition, we have num[1]*num[2] possibilities, and for the second one, we have num[2]*num[1] possibilities. Thus

    num[4] = num[3] * 2 + num[1] * num[2] + num[2] * num[1]

    num[5] = num[4] * 2 + num[1] * num[3] + num[2] * num[2] + num[3] * num[1]


Log in to reply
 

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