leetcode-cn.com/problems/un…

题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

二叉搜索树（binary search tree）BST的特点是一个节点的值大于等于它的全部左子树，小于等于它的全部右子树。

思路

穷举，动态规划

四要素：base case、状态（变量，也就是二叉树总数）、选择（根节点的选择的不同吧）、bp函数（实现功能是返回二叉树的数量）

bp函数怎么实现：先找状态转移方程.

整数n，如果分别以1…n做根节点，那他的BFS总数就是:

G(n)=f(1)+f(2)+….+f(n)

那以n做根节点的子树个数f(n)怎么求呢，找一下规律吧

f(1)，只有一种诶，左边没有数，右边的数需要按大小顺序；

f(2)，也只有一种诶，左边1，右边按大小顺序；

f(3),两种，…

好像想错了，f(1)不是一种，而应该是G(0)*G(n-1)，那f(2)就是G(1)*G(N-2)….

整合一下就是:

G(n)=G(0)*G(n-1)+G(1)*G(N-2)+…+G(i-1)*G(n-i)+…+G(n-1)*G(0);

状态转移方程找到了现在就可以暴力解法了。

暴力解法

    public int numTrees(int n) {
        // 定义dp数组
        int[] dp =new int[n+1];
        // base case
        dp[0]=1;
        dp[1]=1;
        //状态转移方程： G(n)=G(0)*G(n-1)+G(1)*G(N-2)+...+G(i-1)*G(n-i)+...+G(n-1)*G(0);
        // 状态1的所有取值，即所有节点当根节点
        for (int i = 2;i <=n;i++){
            // 状态2下的所有取值：即该节点当根节点时的所有情况
            for (int j = 1; j<=i;j++ ){
                // 状态转移方程
                 dp[i] += dp[j-1]*dp[i-j];
            }
           
        }
        return dp[n];

    }
}
复制代码

Debug

    public int numTrees(int n) {
        // if(n==0){return 0;}
        // if(n==1){return 1;}
        int[] dp =new int[n];
        dp[0]=0;
        dp[1]=1;
        for (int i = 2;i <=n;i++){
            for (int j = 1; j<=i;j++ ){
                 dp[i]=dp[j-1]*dp[i-j];
            }
           
        }
        return dp[n];

    }
}
复制代码

分析：int[] dp =new int[n];数组从0开始，所以最大是n-1，所以for里面会超界。改为
int[] dp =new int[n+1];

分析：用3带了一下dp[i]=dp[j-1]*dp[i-j];这一步最终都会到dp[0]都会=0,dp[n]应该是一个累加，每种情况相加。

分析：用3走了一遍 发现因为dp[0]=0,所以dp[2]=dp[0]dp[1]+dp[1]dp[0]=0明显不对呀，dp[0]应该置为1：空二叉树也是一棵搜索二叉树

递归 使用备忘录优化

    private static Map<Integer, Integer> cache = new HashMap<>();

    private int dfs(int n) {
        if (n <= 1)
            return 1;
        else if (cache.containsKey(n))
            return cache.get(n);
        else {
            int c = 0;
            for (int i = 0; i < n; ++i)
                c += dfs(i) * dfs(n - i - 1);
            cache.put(n, c);
            return c;
        }
    }
    
    public int numTrees(int n) {
        return dfs(n);
    }
}



复制代码

作者：meteordream
链接：leetcode-cn.com/problems/un…