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 2 3 4 5

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公式：

 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;
    }
};