We use dynamic programming. Given nodes[1,2,3….n], we could have n roots. If we calculate how many ways to arrange each root, we can just sum them up all ways.
Let’s call stores ways to arrange i nodes in uniqueShapes[i], and to calculate uniqueShapes[i], we just sum uniqueAtI[1],… till uniqueAtI[i].
To calculate uniqueAtI[j] when calculating uniqueShapes[i], j will be the root. There will be j – 1 nodes smaller than j and i – j nodes bigger than j. so j – 1 nodes will be on the left side of root j and i – j node will be on right side of root j.
There are uniqueShapes[j] ways to arrange j node and uniqueShapes[i – j] ways to arrange i – j, and arranging these two groups of nodes are not interfering with each other so we can use product rule:
While calculating uniqueShapes[i], we will iterate through 1…i as root and calculate uniqueAtI for each of them according to
uniqueAtI[j] = uniqueShapes[j - 1]* uniqueShapes[i - j]
class Solution {
public:
int numTrees(int n) {
vector<int> uniqueShapes(n + 1, 0);
vector<int> uniqueShapesAtI(n + 1, 0);
uniqueShapes[0] = 1;
uniqueShapes[1] = 1;
for(int i = 2; i <=n; i ++){
int sum = 0;
for(int j = 1; j <=i; j ++){
uniqueShapesAtI[j] = uniqueShapes[j - 1] * uniqueShapes[i - j];
sum += uniqueShapesAtI[j];
}
uniqueShapes[i] = sum;
}
return uniqueShapes[n];
}
};