The idea: for n, calculate how many trees are there with node n on layer k, **f(n, k)**, so the total number should be **sum[f(n, k)] for k = 1:n**, no multiplication is needed.

note that **f(n, n) = 1**

when k < n,

**f(n, k)** = **sum[f(n-1, j)] for j = k-1:n-1**

**f(n, k)** = **f(n-1, k-1) + f(n, k+1)**

my code is as following:

```
public int numTrees(int n) {
if (n==0 || n==1) return n;
int[] cnt = new int[n+1];
java.util.Arrays.fill(cnt, 1);
cnt[0] = 0;
for (int i = 2; i <= n; i++) {
for (int j = i-1; j > 0; j--) {
cnt[j] = cnt[j+1] + cnt[j-1];
}
}
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += cnt[i];
}
return sum;
}
```