96. Unique Binary Search Trees - cocoder39/coco39_LC GitHub Wiki

96. Unique Binary Search Trees

Consider DP when facing a "how many" problem.

f(n) = numTrees(n) g(i, n) is #bst rooted with i, where 1 <= i <= n 1. f(n) = g(1, n) + g(2, n) + .. g(n, n) 2. g(i, n) = f(i - 1) * f(n - i)

    f(n) = f(0)*f(n-1) + f(1)*f(n-2) + .. f(n-1)*f(0)
         = sum(f(i - 1) * f(n-i)) where 1 <= i <= n
    f(0) = 1;
    f(1) = 1
    f(2) = f(0)*f(1) + f(1)*f(0) = 2
    f(3) = f(0)f(2) + f(1)f(1) + f(2)f(0) = 5

int numTrees(int n) {
        vector<int> nums(n+1, 0);
        nums[0] = 1;
        nums[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < i; j++){
                nums[i] += nums[j] * nums[i-j-1];
            }
        }
        return nums[n];
}

Same idea is used to solve unique bst ii

⚠️ **GitHub.com Fallback** ⚠️