LeetCode: 96 Unique Binary Search Trees

Problem Description

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

The problem is not hard but it's a good example to demonstrate that for the BST structure, there're many variants when given nodes' values of the inorder scan. That is, an inorder scan would not uniquely determine the structure of a BST but it can validate a BST. This problem is basically ask how many BSTs with different preorder we can construct that will have the same inorder values? We can use dynamic programming to solve it: the subproblem is the number of unique BSTs that have the same inorder value from 1 to i, denoted by dp[i]. And there will be n subproblems. To solve a sub problem, we simply enumerate all possible values at the root nodes and compute the result with the previous results stored in dp array.

a C++ Code

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        dp[0] = 1; dp[1] = 1;
        for(int i=2;i<=n;i++){
            for(int root=1;root<=i;root++)
                dp[i] += dp[root-1] * dp[i-root];
        return dp[n];
    }
};