LC 96 Unique binary search tree

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

    }

};

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax