96. Unique Binary Search Trees - Medium

前往題目

想法

• 找規律？

思路

1. DP
2. 0和1個節點是base case
3. 嘗試把每個點當作root，左樹和右樹再各自當成root直到base case就可以推導出當前n總共有幾種樹

例如n=2總共是兩種可能的樹[0,1], [1,0]，n=3是五種，因為[0,2], [1,1], [2, 0] => 2 + 1 + 2 = 5，n=4是14種，因為[0,3], [1,2], [2,1], [3,0] => 5 + 2 + 2 + 5 = 14

Code

網友解答

class Solution {
    Map<Integer, Integer> map = new HashMap();
    public int numTrees(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        int sum = 0;

        // From 1 to n
        // e.g. 4 -> [0,3], [1,2], [2, 1], [3, 0]
        for (int i = 1; i <= n; ++i) {
            if (!map.containsKey(i - 1)) {
                map.put(i - 1, numTrees(i - 1));
            }
            if (!map.containsKey(n - i)) {
                map.put(n - i, numTrees(n - i));
            }
            sum += map.get(i - 1) * map.get(n - i);
        }
        return sum;
    }
}