96. Unique Binary Search Trees

Problem

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

Summary

Given an integer n, find how many binary search trees can be formed using 1 ... n as nodes?

Solution Approach

• Given n, we need to use the numbers 1-n to form binary search trees and determine how many different tree structures there are, then output this count.
• The solution to this problem is DP. dp[n] represents how many different binary search trees can be formed using the numbers 1-n, and F(i,n) represents the number of different binary search trees formed from 1-n with i as the root node. According to the problem statement, we can get this equation: dp[n] = F(1,n) + F(2,n) + F(3,n) + …… + F(n,n) . The initial values are dp[0] = 1, dp[1] = 1. By analyzing the relationship between dp and F(i,n), we can get the following equation: F(i,n) = dp[i-1] * dp[n-i] . For example, [1,2,3,4,…, i ,…,n-1,n], with i as the root node, the number of different binary search trees that can be formed by the left half [1,2,3,……,i-1] and the right half [i+1,i+2,……,n-1,n] are multiplied, which gives the number of different binary search trees formed from 1-n with i as the root node, that is, F(i,n).

Note that because of the inherent properties of a binary search tree, all values in the right subtree must be greater than those in the left subtree. So here we only need the root node to divide the tree into left and right; we no longer need to care about the sizes of the numbers on the left and right sides, only the number of elements.

• Therefore, the state transition equation is dp[i] = dp[0] * dp[n-1] + dp[1] * dp[n-2] + …… + dp[n-1] * dp[0], and the final result required is dp[n] .

Code

package leetcode

func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1
	for i := 2; i <= n; i++ {
		for j := 1; j <= i; j++ {
			dp[i] += dp[j-1] * dp[i-j]
		}
	}
	return dp[n]
}