[leetcode] Unique Binary Search Trees

这题 之前写过 但现在一看 一点思路也没有.
搜索到的答案很巧妙，希望下次看到类似的可以 举一反三

每个含有n个node的binary tree.. 里面每个数字k都可以作为root, 然后左边会有k-1个node, 右边则有n-k-1个node ... 而左边右边的可能性 则会在bottom up的过程中早已计算好,可以直接用
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)

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

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