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.

思路：

递归
自底向上求解动态规划

我的代码：

public class Solution {
    public int numTrees(int n) {
        if(n <= 1)
            return 1 ;
        int count = 0 ;
        for(int i = 1 ; i <= n ; i++ )
        {
            int left = numTrees( i - 1) ;
            int right = numTrees( n - i ) ;
            count += left * right ;
        }
        return count ;
    }
}

View Code

别人代码：

public class Solution {
    public int numTrees(int n) {
        int[] count = new int[n+2];
        count[0] = 1;
        count[1] = 1;
        
        for(int i=2;  i<= n; i++){
            for(int j=0; j<i; j++){
                count[i] += count[j] * count[i - j - 1];
            }
        }
        return count[n];
    }
}

View Code

学到之处：

采用递归的方法会引起重复的计算
递归方式解决问题的方式如果是划分成两个问题那么一般而言可以转换成自底向上的求解方法从而进一步的节约时间
动态规划表达式这次是循环遍历所有的情况（加，减，找最优）本题的动规方程是count[i] = Σ count[0...k] * count[k+1...i-1] 0≤k<i-1
想动态规划方程的时候，可以先从DFS想起来，DFS进行划分，划分之前DP[i] 划分之后DP[k] DP[i-k]，再根据如何合并和划分的书写出来DP[i]= function(DP[k],DP[i-k])

if(n <= 0) return 0;
int[] treeNumber = new int[n+1];
treeNumber[1] = 1;
treeNumber[0] = 1;

for(int i=2; i<=n; i++){
for(int j=0; j<i ;j++){
treeNumber[i] += treeNumber[j]*treeNumber[i-1-j];
}
}

return treeNumber[n];