Unique Binary Search Tree

Analysis

所有的动态规划的题目，都建立在找规律的基础上，所以，拿到题目以后的第一反应，应该是从简单的数据集里，寻找出通用的规律。 对于这道题目，分析了n=1,2,3,4后，可以发现，跟前面的计算结果是有关系的，可以直接运用之前的计算结果。非常典型的动归题目 从1...n中，假设dp[n]为Unique BST的数量，我取k作为root，那么根据BST的性质从1...k-1就必须是在左子树，k+1....n就必须在右子树，对于每一个k就贡献dp[k-1]dp[n-k]个unique BST dp[n] = dp[n-1] + dp[2-1]dp[n-2] + dp[3-1]dp[n-3] + ... + dp[k-1]dp[n-k] + ...+ dp[n-1-1]*dp[n-(n-1)]+ dp[n-1]

note: Here dp[0] == 1

Solution

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

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

        return dp[n];
    }   
}