96. 不同的二叉搜索树

https://leetcode-cn.com/problems/unique-binary-search-trees/

解法一：dp

参考https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F%28i-n%29-G%28i-1%29-%2a-G%28n-i%29

class Solution:
    def numTrees(self, n: int) -> int:
        G = [0] * (n+1)
        G[0] = G[1] = 1
        for i in range(2, n+1):
            for j in range(1, n+1):
                G[i] += G[j-1] * G[i-j]
        return G[n]

解法二：递归

如上图，以3位根的组合总数为左子树形态总数 * 右子树形态总数，即2*2=4

类似95.不同的二叉搜索树 II的思路，对区间[1...n-1]递归，每次以i（i从1~n-1）为根将区间划分为左右子树

注意，当左区间或右区间长度小于0，即无法构造子树（对应空节点）时，子树数=1而不是0

class Solution:
    def numTrees(self, n: int) -> int:
        def countTrees(start, end):
            if start > end:
                return 1
            res = 0
            for i in range(start, end+1):
                left = countTrees(start, i-1)
                right = countTrees(i+1, end)
                res += left * right
            return res
        return countTrees(1, n)

然而超时，当n=19

改进

上面暴力递归穷举会重复计算，例如[1...2]这个区间会重复计算多次，而该区间的结果一旦计算出来是不变的，考虑使用备忘录

class Solution:
    def numTrees(self, n: int) -> int:
        memo = [[0]*(n+1) for _ in range(n+1)]
        def countTrees(start, end):
            if start > end:
                return 1
            if memo[start][end] != 0:   #备忘录有记录，直接返回
                return memo[start][end]
            res = 0
            for i in range(start, end+1):
                left = countTrees(start, i-1)
                right = countTrees(i+1, end)
                res += left * right
            memo[start][end] = res  #得到结果写备忘录
            return res
        return countTrees(1, n)