算法

(DP) $O(n^2)$

定义状态：f[i]：表示长度为i的节点可构造出多少种bst

状态转移方程：$f(n) = sum(f(i - 1) * f(n - i)) i:[1, n]$ ，也就是分别以不同的节点为根构造出bst，方法数由乘法原理和加法原理即可得到

初始条件：$f[0] = 1$

Java 代码

class Solution {
    public int numTrees(int n) {
        // [1, 2, ... i  ... n]
        // [1, i - 1] i [i + 1, n]
        // f(i - 1) * f(n - i)
        // f(n) = sum(f(i - 1) * f(n - i)) i:[1, n]
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }
}

Python 代码

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