Leetcode 96 Solution

This article provides solution to leetcode question 96 (unique-binary-search-trees).
Categories:
Tags:
Access this page by simply typing in "lcs 96" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/unique-binary-search-trees

Solution

class Solution {
public:
    int numTrees(int n) {
        vector<int> a;
        a.resize(n + 1);
        
        a[0] = 1;
        a[1] = 1;
        
        for (int i = 2; i <= n; i++)
        {
            a[i] = 0;

            for (int j = 0; j <= i - 1; j++)
            {
                a[i] += a[j] * a[i - 1 - j];
            }
        }
        
        return a[n];
    }
};