Leetcode OJ平台上的UniqueBinarySearch Trees题目用Java实现

题目如下，意思就是说，给定n个节点，最多能有多少个形状不重复的二叉树

Givenn, how many structurally uniqueBST's(binary search trees) that store values 1...n?

For example,
Givenn= 3, there are a total of 5 unique BST's.

1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

苦思冥想了很久，想找一个数学规律出来，然后失败了。
万能的木易先森提醒：
f(3) = f(2)*f(0) + f(1)*f(1)+f(0)*f(2)...
f(4) = f(3)*f(0) + f(2)*f(1) + f(1)*f(2) + f(0)*f(3)...

将f(0)初始化成1，然后使用迭代的方法，计算出f(n)。

import java.util.ArrayList;

public class Solution {
public static int numTrees(int n) {
ArrayList a = new ArrayList(n);
a.add(1);
a.add(1);
a.add(2);
a.add(5);
for(int i = 4; i <= n; i ++){
int tmp = 0;
for(int j = 0; j < i; j ++){
tmp += (Integer)(a.get(j)) * (Integer)(a.get(i-1-j));
}
a.add(tmp);
}
return (Integer) a.get(n);

}

public static void main(String args[]){
int num = numTrees(4);
System.out.println(num);
}
}