Leet Code -- Unique BST

  2    1

   1                                              2                                                  3                                                     4                                     

  2,3,4,5(14种)             （1种）1   3,4,5（5种）           （2种）1,2  4,5（2种）               （5种）1,2,3  5（1种）               

        5

      /

1,2,3,4（14种）

public class Solution {
    public int NumTrees(int n) {
        if(n <= 0) {
		return 1;
	}
	
	// - dp array
	var dp = new int[n+1];
	dp[0] = 1;
	dp[1] = 1;
	
	for(var j = 2; j <= n; j++){
		// i: 1.. j
		// dp[j] = sum (dp[i-1] * dp[j-i])
		var s = 0;
		for(var i = 1; i <= j; i++){
			s += dp[i-1] * dp[j-i];
		}
		
		dp[j] = s;
	}
	
	return dp[n];
    }
}

Leet Code -- Unique BST

原文：http://blog.csdn.net/lan_liang/article/details/47020365