[leetcode] unique binary search trees

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int cache[n];
       
        for (int i = 0; i < n; i++)
            cache[i] = 0;
       
        cache[0] = 1;
       
        for (int i = 1; i < n; i++)
        {
            // compute the count for N = i+1 nodes
            int count = 0;
            for (int k = 0; k <= i; k++)
            {
                // assume [0..i] is computed
                // pick k as the root
                int left_sum = 1, right_sum = 1;
               
                if (k > 0)
                    left_sum = cache[k-1];
               
                if (k < i)
                    right_sum = cache[i-k-1];
                   
                count += left_sum*right_sum;
            }
            cache[i] = count;
        }
       
        return cache[n-1];
    }
};