20ms C++ top-down DP solution


  • 11
    R

    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;
    }

  • -9
    J

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


  • 0
    C

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


  • 0
    S

    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.