[数据结构与算法]LeetCode热题HOT-100 96、不同的二叉搜索树

题目链接

思路：动态规划

• 我们假设恰由n个节点组成的二叉搜索树的数目为G(n)
• 再假设根结点为i(1 <= i <= n)的、有n个结点的二叉搜索树的数目为F(i,n)个
• 那么自然有 G(n) = F(1,n) + F(2,n) + F(3,n) + ······ + F(n,n)
• 又因为F(i,n) = G(i-1) * G(n-i) (以i为根节点且共有n个结点的二叉搜索树的数目为 左子树可能的数目(G(i-1))*右子树可能的数目G(n-i))
• 所以可以得到最终的结果为 G(n) = G(0)*G(n-1) + G(1)*G(n-2) + ······ + G(n-1)*G(0)
• 与此同时，G(0) = 1 G(1) = 1(G(0)代表空树，所以只有一种情况)
• 所以要计算G(n) 必须要知道G(n-1),而要知道G(n-1)又必须要知道G(n-2),因此我们必须要从3开始依次计算

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;

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