AC solution, O(n^2) without muliplication or division


  • 0
    B

    The idea: for n, calculate how many trees are there with node n on layer k, f(n, k), so the total number should be sum[f(n, k)] for k = 1:n, no multiplication is needed.

    note that f(n, n) = 1
    when k < n,
    f(n, k) = sum[f(n-1, j)] for j = k-1:n-1
    f(n, k) = f(n-1, k-1) + f(n, k+1)

    my code is as following:

    public int numTrees(int n) {
        if (n==0 || n==1) return n;
        int[] cnt = new int[n+1];
        java.util.Arrays.fill(cnt, 1);
        cnt[0] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = i-1; j > 0; j--) {
                cnt[j] = cnt[j+1] + cnt[j-1];
            }
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += cnt[i];
        }
        return sum;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.