# Java solution, DP with n^2 time

• 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];
}
}
}``````

• 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];
}
}
``````

}

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

• ``````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];
}``````

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