# DP using C++(20ms)

• ``````class Solution {
public:
vector<vector<vector<TreeNode*> > > dp;
vector<vector<bool> > test;

vector<TreeNode*> search(int left, int right){
vector<TreeNode* > vec;
if(left > right){
vec.push_back(NULL);
return vec;
}

if(test[left][right]) return dp[left][right];

for(int i = left; i <= right; i ++){
vector<TreeNode *> ltree = search(left, i - 1);
vector<TreeNode *> rtree = search(i + 1, right);

for(int j = 0; j < ltree.size(); j ++){
for(int k = 0; k < rtree.size(); k ++){
TreeNode* root = new TreeNode(i);
root->left = ltree[j];
root->right = rtree[k];
vec.push_back(root);
}
}
}

dp[left][right] = vec;
test[left][right] = true;
return vec;
}

vector<TreeNode*> generateTrees(int n) {
for(int i = 0; i <= n; i ++){
vector<bool> v(n + 1, false);
test.push_back(v);

vector<vector<TreeNode*> > vv(n + 1, vector<TreeNode*>(n+1, NULL));
dp.push_back(vv);
}

return search(1, n);
}
``````

};

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