Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/description/

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

Thoughts

不会做。看到https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i/2 解释的很好。

让G(n)表示长度为n的数列能形成的unique binary tree的数目，注意这里的G不仅代表了[1, ..., n], 而是任意[i, ...., i+ n-1]的能组成的数目。因为[1, ..., n]组成的bst和[i,..., i+ n -1] 能构成的bst数目是一致的，认清这点 非常重要 。F(i, n)表示以i为root的前n个元素能形成的unique bin tree个数, 那么f[i][n] = G(i-1) * G(n-i), 分别对应了左子树和右子树可能的情况。又因为G(n) = f(1, n) + f(2, n) + ...+ f(n, n).

合并两个式子能得到G(n) = G(0) * G(n-1) + G(1) * G(n-2) ... + G(n-1)*G(0).

Code

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

        return G[n];
    }
}

Analysis

时间复杂度为O(n^2).