//DP solution
//Time: O(n^2), 0ms
//Space: O(n)
class Solution {
    public int numTrees(int n) {
        //Initialize the table with margin
        int[][] table = new int[n + 2][n + 2];
        //Base case
        for(int i = 0; i < n + 2; i++) {
            for(int j = 0; j <= i; j++) {
                table[i][j] = 1;
            }
        }
        //Fill in the table diagnally
        for(int i = 1; i < n; i ++) {
            for(int j = 1; j < n + 1 - i; j++) {
                for(int k = j; k <= i + j;k++) {
                    table[j][i + j] += table[j][k - 1] * table[k + 1][i + j];
                }
            }
        }
        /*
        for(int i = 0; i < n + 2; i++) {
            for(int j = 0; j < n + 2; j++) {
                System.out.print(table[i][j] + " ");
            }
            System.out.println();
        }
        */
        //Return the top right corner
        return table[1][n];
    }
}