96. Unique Binary Search Trees

给定1到n这n个数，用它们能够构成多少种形状不同的二叉搜索树。

思路：动态规划，dp[i]表示i 个数字能组成的树的个数，状态转移方程： dp[0], dp[1], dp[2] = 1, 1, 2, 对于n>2, dp[n] = dp[0]dp[n-1] +dp[1]dp[[n-2] + ..+dp[n-1]*dp[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 6 star, 动态规划， 需多练
        if n < 3:
            dp = [1, 1, 2]
            return dp[n]
        else:
            dp = [0 for _ in range(n+1)]
            dp[:3] = [1, 1, 2]
            for i in range(3, n+1):
                for j in range(i):
                    dp[i] += dp[j] * dp[i-j-1]
            return dp[-1]

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 7 star, 未能想出来，难点在于发现规律，dp[i] = dp[0]*dp[i-1] + dp[1]*dp[i-2] + ... + dp[i-1]*dp[0]
// dp[i]表示i个数字的可以组成的独特的二叉查找树的个数，左边0个右边i-1个，左边1个右边i-2个，一直到到左边i-1个右边0个，这些情况的总和即是dp[i]
func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1
	for i := 2; i<n+1; i++ {
		for j:=0; j<i; j++ {
			dp[i] += dp[j] * dp[i-1-j]
		}
	}
	return dp[n]

}