Unique Binary Search Trees

Unique Binary Search Trees

---

今天的题目是一道动态规划的题目,来自LeetCode，标号96。该题的难度为Medium，Acceptance为35.8%。

题目如下：

Given n, how many structurally unique BSTs (binary search trees) that store values 1...n ?
Example Given n = 3, there are a total of 5 unique BST's.

dp

思路如下：

熟悉动态规划的同学肯定是做过这道题目的，思路也较为清晰。

首先，设有n个节点；从中选取一个节点k作为根节点，共有n种取法。因为是二叉搜索树，则以这个k节点为根的二叉树的左子树和右子树都是二叉搜索树，且左子树的节点个数为k-1，右子树的节点个数为n - k。

然后，分别求出左子树的个数和右子树的个数，相乘之后就可以得到取k为根节点时的二叉树的个数，k可以从1 到 n之间取值，则可以得到递推公式：

公式

其中，i表示左子树节点个数，即此时k = i + 1，则右子树的个数为n - i - 1。

代码如下

java版

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

C++版

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