算法练习：不同的二叉搜索树（动态规划）

一.前言

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

示例 1：

输入：n = 3
输出：5

示例2：

输入：n = 1
输出：1

题目很简洁，但是分析起来却有点复杂，首先搞清楚什么是二叉搜索树。二叉搜索树分为左子树和右子树，左子树还能再分为左子树和右子树，就像这样：

二叉搜索树有三个条件：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
它的左、右子树也分别为二叉搜索树

二.分析思考

我们将 dp 数组定义为 1 到 n 互不相同的二叉搜索树的个数，先来尝试写写 n = 1 和 n = 2的情况

这两个其实还挺简单的，再来看看 n = 3 的时候

这个时候不同的二叉搜索树就有 5 个了，我们来看看这五个是怎么根据前面的结果推导出来的。此图片中前两棵树是根据 dp[2]中的第一个二叉搜索树得出来的，他们结构都是一样的，都是没有左子树，右子树有两个结点。而 dp[3]中的第三和第四棵树同理和 dp[2]中的第二棵树结构相同。

那么 dp[3]中最后一棵树是怎么来的呢，我们将眼光放宽一点，这时候会发现它和 dp[1]中那棵树结构很相似！

继续探索一下这个规律：

二叉搜索树当以 1 为起点时，它的个数为右子树的个数 dp[2]；
二叉搜索树当以 2 为起点时，它的个数为右子树的个数 dp[1] * 左子树的个数 dp[1]；
二叉搜索树当以 3 为起点时，它的个数为左子树的个数 dp[2]；
则总共的二叉搜索树为：dp[2] + dp[1] * dp[1] + dp[2]
注：定义 dp[0] = 1，使之符合下面通式的规律

我们将这个规律扩展到 n，我们需要计算出从 1 到 n 为起点的每一个二叉搜索树的个数，因此需要循环来遍历，则总共的二叉搜索树为：dp[i] += dp[i - j] * dp[j -1]，其中i 为外层循环且i <= n，j 为内层循环且 j <= i。
为了验证一下这个规律，我们继续往下写一组二叉搜索树，当n = 4时

其中二叉搜索树为个数为：dp[0] * dp[3] + dp[1] * dp[2] + dp[2] * dp[1] + dp[3] * dp[0] = 14，确实符合上述规律…

三.代码

分析完了，现在就来看看代码，如果还有点疑惑说不定看了代码就豁然开朗了。

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