if you comment the code between //code-start and //code-end, the running time will up to exceed 1000ms.

this code avoid redundant calculation of the same size BST, because any sequence with the same size has the same BST number. for example, {1,2,3} has 5 BST, so does {1,2,4},{4,5,6}, ...{a,b,c}...

class Solution {

public:

```
int divideTrees(int start, int end, map<int,int> &mp)
{
if(start >= end)
{
return 1;
}
int k = end-start+1;
//code-start
if(mp.find(k) != mp.end())
{
return mp[k];
}
//code-end
int res = 0;
for(int i = start; i <= end; ++i)
{
int res1 = divideTrees(start, i-1, mp);
int res2 = divideTrees(i+1,end,mp);
res += res1*res2;
mp[i-1-start+1] = res1;
mp[end-i-1+1] = res2;
}
return res;
}
int numTrees(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
map<int,int> mp;
mp[1] = 1;
mp[2] = 2;
return divideTrees(1,n,mp);
}
```

};