96. 不同的二叉搜索树

题意：

解题思路：

思路1:
动态规划
假设n个节点存在
令G(n)的从1到n可以形成二叉排序树个数
令f(i)为以i为根的二叉搜索树的个数
即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
1. n为根节点，当i为根节点时，
2. 其左子树节点个数为[1,2,3,...,i-1]，
3. 右子树节点个数为[i+1,i+2,...n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
上面两式可得:G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)
N cnt  组合
1  1   [1]       => 1种
2  2   [12] [21] => 2种
3  5   1 2 3     => 5种
针对i = 3，
当选择1为根节点时:dp[1-1] * dp[3-1] => dp[0] * dp[2] ：左边没有节点，右边有2个节点，可以组成：[123]，[132]
当选择2为根节点时:dp[2-1] * dp[3-2] => dp[1] * dp[1] ：左边一个节点，右边一个节点，可以组成：[中左右]:[213]
当选择3为根节点时:dp[3-1] * dp[3-3] => dp[2] * dp[0] ：左边2个节点，右边没有节点，可以组成：[3,2,1][3,1,2]
所以当选择3时：dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0] = 5
得出递推公式：d[i] = d[j-1] * d[$i-j];
j = 1~i;=>j从1遍历到i，最后返回dp[n]
思路2：
对于每一个根i他都是由左边子树（1, 2, ..., i - 1)和右边子树（i + 1, i + 2, ..., n)组成的。
因此他的个数肯定是两个子树情况的积。而且，这种根一共有n个，再将这些加起来就可以了。

PHP代码实现：

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function numTrees($n) {
        //return $this->numTrees1($n);
        if ($n <= 1) return 1;
        $dp[0] = 1;
        $dp[1] = 1;
        for ($i = 2; $i <= $n; $i++) {
            for ($j = 1; $j <= $i; $j++) {
                //左子树：$dp[$j - 1]
                //右子树：$dp[$i - $j]
                $dp[$i] += $dp[$j - 1] * $dp[$i - $j];
            }
        }
        return $dp[$n];
    }
    function numTrees1($n) {
        if ($n <= 1) return 1;
        $res = 0;
        for ($i = 0; $i < $n; $i++) {
            $res += $this->numTrees1($i) * $this->numTrees1($n - $i - 1);
        }
        return $res;
    }
}

GO代码实现：

func numTrees(n int) int {
    G := make([]int, n + 1)
    G[0], G[1] = 1, 1
    for i := 2; i <= n; i++ {
        for j := 1; j <= i; j++ {
            G[i] += G[j-1] * G[i-j]
        }
    }
    return G[n]
}