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. 如果以1root结点,则右边2~3F(2)=f(2~3)个解
  2. 如果以2root,则左边有F(1)=f(1~1)、右边有F(1)=f(3~3);总F(1)*F(1)
  3. 如果以3root,则左边有F(2)=f(1~2)

对于13两种情形,左边/右边有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;
    }
};