# Simple C code in 1ms, DP, a little different from other solutions.

• ``````int solutions[1024]={1,1,};
int calculated = 1;
int numTrees(int n) {
//f(n)=sum(i=0,i<n)[f(i)*f(n-i-1)]
if(n<calculated)
return solutions[n];
int start = calculated+1;
for(int loop = start;loop<n+1;loop++){
int sum = 0;
for(int i=0;i<loop;i++){
sum += solutions[i]*solutions[loop-i-1];
}
solutions[loop]=sum;
}
calculated = n;
return solutions[n];
}
``````

The array `solutions` is declared as a global variable, that's reasonable.

Assuming that this function will be called quite frequent, calculating `solutions[2],solutions[3], ... ,solutions[i]` will costs a lot time.

For example, at the beginning, `numTrees(10)` is called.

We will get solutions[0] to solutions[10], then return solutions[10], finished.

Next time, `numTrees(5)` is called.

If we didn't save the array `solutions`, we must calculate them again.

If we saved the results in `numTrees(10)` as `solutions[ ]`, we can return `solutions[5]` directly without any calculation.

In my code, I use global variable.

But obviously, `static` is a better way.

`static solutions[1024] = {1,1,};`

`static calculated;`

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