Unique Binary Search Trees解题报告

Description:

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

For example,
Given n = 3, there are a total of 5 unique BST's.

Example:

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

Link:

https://leetcode.com/problems/unique-binary-search-trees/description/

解题方法：

初看到这道题，一点头绪都没有，但是在纸上画出n = 0, 1, 2, 3, 4情况以后，才意识到这是道动态规划的题。
如果当n = 0时，只有一种情况就是空树；
当n = 1时，也只有一种情况；

1

当n = 2时，有两种情况：

1                2 
  \             /
    2          1

当n = 3时，其实已经可以看出规律，每当加上一个最大节点，根据这个最大节点和之前节点所构成的树无非是以下这一种形状：

部分之前节点（节点个数可能为0，1，2个）
      \
       \
     当前最大节点（3）
        /
       /
部分之前节点（节点个数可能为0，1，2个）

当最大节点确定时，只会有以上这种构造情况，由此，根据当前最大节点上面有多少个节点和下面有多少个节点，可以推出动态规划的方程：

dp[i] = dp[0] * dp[i - 1 - 0] + dp[1] * dp[i - 1 - 1] + ... + dp[j] * dp[i - 1 - j] + dp[i - 1] * dp[0]

Time Complexity：

O(N^2)

完整代码：

int numTrees(int n) 
    {
        vector<int> dp(n + 1, 0);
        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];
    }