Description

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3

Output: 5

Explanation: Given n = 3, there are a total of 5 unique BST’s:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution

以n = 3为例，有数字1、2、3；设解为F(3)=f(1~3)；

对F(3)分解：

  1. 如果以1为root结点，则右边2~3有F(2)=f(2~3)个解
  2. 如果以2为root，则左边有F(1)=f(1~1)、右边有F(1)=f(3~3)；总F(1)*F(1)
  3. 如果以3为root，则左边有F(2)=f(1~2)

对于1和3两种情形，左边/右边有0个数，我们设为F(0)=1。

最终：F(3) = F(0)*F(2) + F(1)*F(1) + F(2)*F(0)个解。

所以可推导出DP公式：

$$ F(n) = \sum_{i=0}^{n}F(i) * F(n-i-1) ; F(0) = 1; $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numTrees(int n) {
        int *dp = new int[n+1]{1, 1};  // {F(0), F(1)}

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

        int r = dp[n];
        delete []dp;
        return r;
    }
};