Unique Binary Search Trees (LeetCode) | Dynamic Programming

UniqueBinarySearchTrees.cpp

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1, 0);
        G[0] = 1, G[1] = 1;
        
        // Iterating for different values of N, in Bottom Up Approach
        for(int i = 0; i <= n; ++i) {
            
            // Looking at each case with all nodes as roots
            for(int j = 1; j <= i; ++j) {
                // Number of total trees possible for current value of i:
                // Possibilities for left subtree  x  Possibilities for right subtree
                G[i] += G[j - 1] + G[i - j];
            }
        }
        return G[n];
    }
};