# DP solution in C++

• using a map to record trees generated with numbers between i and j inclusive.
for each number in 1 to n choose it as root node, then generate left trees and right trees with a dfs algorithm

``````class Solution {public: map<pair<int,int>, vector<TreeNode *> >::iterator it;
void generateTrees(int b, int e, map<pair<int,int>, vector<TreeNode *> >& dp)
{
if(b>e)
{
return;
}
it=dp.find(pair<int,int>(b,e));
if(it!=dp.end())return;
vector<TreeNode *>& res=dp[pair<int,int>(b,e)];
for(int i=b;i<=e;i++)
{
generateTrees(b,i-1,dp);
generateTrees(i+1,e,dp);
if(b>(i-1)&&(i+1)>e)
{
TreeNode* tn=new TreeNode(i);
res.push_back(tn);
}
if(b>(i-1))
{
vector<TreeNode *>& v2=dp[pair<int,int>(i+1,e)];
for(int k=0;k<v2.size();k++)
{
TreeNode* tn=new TreeNode(i);
tn->right=v2[k];
res.push_back(tn);
}
}
if((i+1)>e)
{
vector<TreeNode *>& v1=dp[pair<int,int>(b,i-1)];
for(int j=0;j<v1.size();j++)
{
TreeNode* tn=new TreeNode(i);
tn->left=v1[j];
res.push_back(tn);
}
}
else
{
vector<TreeNode *>& v1=dp[pair<int,int>(b,i-1)];
vector<TreeNode *>& v2=dp[pair<int,int>(i+1,e)];
for(int j=0;j<v1.size();j++)
{
for(int k=0;k<v2.size();k++)
{
TreeNode* tn=new TreeNode(i);
tn->left=v1[j];
tn->right=v2[k];
res.push_back(tn);
}
}
}
}
}
vector<TreeNode *> generateTrees(int n) {
vector<TreeNode *> res;
map<pair<int,int>, vector<TreeNode *> > dp;
if(n==0)
{
res.push_back(0);
return res;
}
generateTrees(1,n,dp);
return dp[pair<int,int>(1,n)];
}};``````

• Actually I can make the code shorter, however it can't pass the compiler in OJ

below solution can pass compiler in VS2010

``````class Solution {public:
map<pair<int,int>, vector<TreeNode *> >::iterator it;
void generateTrees(int b, int e, map<pair<int,int>, vector<TreeNode *> >& dp)
{
if(b>e)
{
return;
}
it=dp.find(pair<int,int>(b,e));
if(it!=dp.end())return;
vector<TreeNode *>& res=dp[pair<int,int>(b,e)];
for(int i=b;i<=e;i++)
{
generateTrees(b,i-1,dp);
generateTrees(i+1,e,dp);

vector<TreeNode *>& v1=b<=(i-1)?dp[pair<int,int>(b,i-1)]:vector<TreeNode *>(1,0);
vector<TreeNode *>& v2=(i+1)<=e?dp[pair<int,int>(i+1,e)]:vector<TreeNode *>(1,0);
for(int j=0;j<v1.size();j++)
{
for(int k=0;k<v2.size();k++)
{
TreeNode* tn=new TreeNode(i);
tn->left=v1[j];
tn->right=v2[k];
res.push_back(tn);
}
}
}
}
vector<TreeNode *> generateTrees(int n) {
vector<TreeNode *> res;
map<pair<int,int>, vector<TreeNode *> > dp;
if(n==0)
{
res.push_back(0);
return res;
}
generateTrees(1,n,dp);
return dp[pair<int,int>(1,n)];
}};
``````

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