0ms 10line dp c++ solution with explain

  • 4

    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];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=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.