# Simple C++ DP solution

• ``````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];
}``````

• 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

• How much time do u spend to solve this problem?

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

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

• @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 :)

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

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