[leetcode] Unique Binary Search Tree

Essentially a DP problem
number[i] = number[0] * number[i-1] + number[1]*number[i-1-1]......number[i-1]*number[0]
左边有n Node的时候 右边最多只有 i-n-1 因为有一个在中间。。。而这些都是已经算过了的

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public class Solution { public int numTrees(int n) { int check[] = new int[n+1]; check[0] = 1; check[1] = 1; for (int i = 2; i <= n; i++){ check[i] = 0; for (int j = 0; j <= i-1; j++){ check[i] += (check[j]*check[i-j-1]); } } return check[n]; } }