Java solution, DP with n^2 time


  • 0
    J

    I thought this is efficient code but actually it falls into the slower half of Java solutions, anybody can point out any reason?
    It's straightforward though, so if anyone doesn't have a clue, this may help :)

    public int numTrees(int n) {
        int[] v = new int[n + 1];   // v[n] is the number of trees with n values
        v[0] = 1;
        v[1] = 1;
        numTrees(v, n);
        return v[n];
    }
    
    private void numTrees(int[] v, int n) {
        for(int i=2; i<=n; i++) {
            for(int j=0; j<i; j++) {
                v[i] += v[j] * v[i-j-1];
            }
        }
    }

  • 0
    S

    private void numTrees(int[] v, int n) {

    for(int i=2; i<=n; i++) {
        v[i]=0;
        for(int j=0; j<i; j++) {
            v[i] += v[j] * v[i-j-1];
        }
    }
    

    }


  • 0
    J

    You don't need to initialize actually, it's by default 0. But it may be good practice.


  • 0
    public int numTrees(int n) {
        int[] a = new int[n+1];
        a[0] = 1;
        return compute(a, n); 
    }
    
    private int compute(int[] a, int n) {
        for (int i = 1; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                a[i] += a[j] * a[i-j-1];
            }
        }
        return a[n];
    }

Log in to reply
 

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