本文共 908 字，大约阅读时间需要 3 分钟。

链接：

大意：

给定一个整数n，以1~n为树节点元素值构建BST。求有多少种BST

思路：

动态规划。

假设 n = k时有dp[k]种可能形式，则当n = k + 1时，对根顶点分类讨论

    1. 当根顶点为k+1时，此时左子树有k个数，右子树有0个数。而这k个数刚好是1~k，因此左子树有dp[k]种形式，而右子树为null，只有一种形式     2. 当根顶点为k时，此时左子树有k-1个数（由于是BST，所以左子树的数为1~k-1），因此左子树有dp[k - 1]种形式；而右子树有一个数（k+1），只有一种形式     3. 当根顶点为k-1时，此时左子树有k-2个数（1~k-2），因此左子树有dp[k-2]种形式；而右子树有2个数（k，k+1），两个数有dp[2]种形式     4. 当根顶点为k-2时，此时左子树有k-3个数（1~k-3），因此左子树有dp[k-3]种形式；而右子树有3个数（k-1，k，k+1），三个数有dp[3]种形式     ...     直到根顶点为1

代码：

class Solution {    public int numTrees(int n) {        if (n <= 0)            return 0;        int[] dp = new int[n + 1]; // dp[i]:当只有i个数时，有多少种BST        dp[0] = 1;        dp[1] = 1;        int i = 2;        while (i <= n) {            int rem = i - 1;            while (rem >= 0) {                dp[i] += dp[rem] * dp[i - 1 - rem];                rem--;            }            i++;        }        return dp[n];    }}

结果：

结论：

很巧妙的一个动态规划。如果没有看 Related Topics，估计渣渣的我是难以想出的... 

 

 

转载地址：http://atesi.baihongyu.com/