# 20ms C++ top-down DP solution

• a bottom up solution looks much better, but I find it's also a little bit harder to understand. Top-down solution is straight forward,

``````vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> ret;
vector<vector<vector<TreeNode*>>> dp(n,vector<vector<TreeNode*>>(n));
helper(1,n,ret,dp);
return ret;
}

void helper(int start, int end, vector<TreeNode*> &ret,vector<vector<vector<TreeNode*>>> &dp) {
if (start > end) {
ret.push_back(NULL); return;
}
if (!dp[start-1][end-1].empty())  {
ret = dp[start-1][end-1]; return;
}
for (int i = start; i <= end; ++i) {
vector<TreeNode*> left, right;
helper(start, i-1,left,dp);
helper(i+1,end,right,dp);
for(int j = 0; j < left.size(); ++j) {
for (int k = 0; k < right.size(); ++k) {
TreeNode* node = new TreeNode(i);
node->left = left[j];
node->right = right[k];
ret.push_back(node);
}
}
}
dp[start-1][end-1] = ret;
}``````

• when talking about top-down,are you meaning top to down?
I believe that top - down means from top to down,right?

• Strictly speaking, this is recursive with buffering. Pretty nice implementation.

• The time complexity without memoization is 2^n , so the time complexity of such an approach should be lesser than this. Can some one point out what is the time complexity of this ?

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