Unique Binary Search Trees

题目：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.

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

思路：

假设从1到n，那么，那么可以选取任何一个做根节点。假设选择i，那么左边只能是1-i-1，右边是i+1 - n，所以有公式

f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+...+f(n-1)*f(0)。

使用动态规划轻松解出。

代码：

class Solution {
public:
    int numTrees(int n) {
        //https://leetcode.com/problems/unique-binary-search-trees/
        // f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+...+f(n-1)*f(0)
        //f(1)=f(0)*f(0)   f(2)=f(0)*f(1)+f(1)*f(0)
        //f(3)=f(0)*f(2)+f(1)*f(2)+f(2)*f(0)
        vector<int> sum(n+1,0);
        sum[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                sum[i]+=sum[j]*sum[i-1-j];
            }
        }
        
        return sum[n];
    }
};