1
class Solution {
2
  public int numTrees(int n) {
3
    // Create 'sol' array of length n+1...
4
    int[] sol = new int[n + 1];
5
    // The value of the first index will be 1.
6
    sol[0] = 1;
7
    // Run a loop from 1 to n+1...
8
    for (int i = 1; i <= n; i++) {
9
      // Within the above loop, run a nested loop from 0 to i...
10
      for (int j = 0; j < i; j++) {
11
        // Update the i-th position of the array by adding the multiplication of the respective
12
        // index...
13
        sol[i] += sol[j] * sol[i - j - 1];
14
      }
15
    }
16
    // Return the value of the nth index of the array to get the solution...
17
    return sol[n];
18
  }
19
}