0ms 10line dp c++ solution with explain


  • 4
    Z

    when ask f(n),the root of possible tree can be 1,2...n,if the root is i,the possible number f(n,i) is the possible number of the left tree multiply by the right;the elements of left child tree is 1...i-1, number is i-1; the right is i+1...n,number is n-i;so f(n,i)=f(i-1)*f(n-i),f(n)=sum( f(n,i) )

    int numTrees(int n) {
        int dp[10000];
        dp[0]=1;
        for(int i=1;i<=n;i++){
            dp[i]=0;
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

Log in to reply
 

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