Simple C++ DP solution


  • 6
    I
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
    	    for (int j = 0; j < i; j++) {
    		    dp[i] += dp[j] * dp[i - 1 - j];
    	    }
        }
        return dp[n];
    }

  • 0
    A

    My solution is almost exactly the same as yours. I used an array and named it "solution", literally everything else is exactly the same :o


  • 0

    How much time do u spend to solve this problem?


  • 0
    I

    I don't remember... >_<|||


  • 0
    R

    please explain code...how u came to this logic???


  • 0
    I

    @ravi007 dp[i] represents the number of structurally unique trees of i nodes. For example, we have four nodes now, and we have already known the number of trees of 0, 1, 2, 3 nodes(we have already calculated dp[0], dp[1], dp[2], dp[3]). Then how do we get the dp[4]? We can first take 1 node out, and let's call it 'root', then we have 3 nodes left. After that, we can create a new unique structurally unique tree by putting a tree 0-node-tree on left side of 'root' and putting a 3-node-tree on right side of it. And how many ways are there for us to do this? The answer is dp[0] * dp[3]. For the same reason, we can put 1-node-tree on the left and 2-node-tree on the right, 2-node-tree on the left and 1-node-tree on the right, 3-node-tree on the left and 0-node-tree on the right. That's all.
    Thus dp[4] = d[0] * dp[3] + dp[1] * d[2] + dp[2] * dp[1] + dp[3] * dp[0].
    I hope I've made myself understood :)


  • 0
    R

    @Irving_cl thanks bro!!! got it...


Log in to reply
 

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