96. Unique Binary Search Trees

Link

Solution

BST 的組成方式可依照以誰當root來分

當我們選擇i-th element當作root，那麼則會有 i-1 個element在左子樹， n-i個在右子樹 以i-th element當root的所有組合數為左右子樹的可能數相乘， dp[i-1] * dp[n-i] 所以就可以簡化成 dp[n] += dp[i-1] * dp[n-i] // for i = 1 -> n(表示選ith element當root), dp[0] = 1, dp[1] = 1

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