96. Unique Binary Search Trees

http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html
二刷

Typical DP
dp[i] -> num of trees for input number n
100.00 %
class Solution {
    public int numTrees(int n) {
        // n = 0 -> 1
        // n = 1 -> 1
        // n = 2 -> 1 root (0, 1), (1, 0) -> 1*1 + 1*1 = 2
        //   i        k
        //   0  1  2  3
        // n = 3 -> 1 root (0, 2), (1, 1), (2, 0) -> 1*2 + 1*1 + 2*1 = 5
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int k = 2; k <= n; k++) {
            for (int i = 0; i < k; i++) {
                dp[k] += dp[i] * dp[k - 1 - i];
            }
        }
        return dp[n];
    }
}

一刷
自己是想不出来的
其实思路很简单
所有子问题都是同一个问题
[4, 5, 6, 7] 和 [1, 2, 3, 4] 能生成的tree的种类是一样的
所以只需要iter一下左右各能分多少个，然后把左右的可能性相乘，就是当前的可能性
13.74 %
public class Solution {
    public int numTrees(int n) {
        if (n <= 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int k = 1; k <= i; k++) {
                dp[i] += dp[k - 1] * dp[i - k];
            }
        }
        return dp[n];
     
    }
}