This is my AC code ,1ms.


  • 0
    L

    The problem of catalan.
    f[n]=2*(2n-1)f[n-1]/n+1;
    int numTrees(int n) {
    int i;
    double f1,f2;
    f1 = 1.0;
    f2 = 1.0;
    for (i = 2;i<=n;i++)
    {
    f2 = (2
    i-1)
    (2*f1/(i+1));
    f1 = f2;
    }
    return (int)f2;
    }


  • 0
    Z

    my solution is same to you , is there any better solution?

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

Log in to reply
 

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