20ms C++ top-down DP solution

  • 11

    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));
        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);
            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];
        dp[start-1][end-1] = ret;

  • -9

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

  • 0

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

  • 0

    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 ?

Log in to reply

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