Recursive and DP Solution in java


  • 0
    Y
    public class Solution {
        // recursive
        public int numTrees2(int n) {
            if (n == 0 || n == 1) {
                return 1;
            }
            else {
                int sum = 0;
                for (int i = 1; i <= n; i++) {
                    sum += numTrees(i - 1) * numTrees(n - i);
                }
                return sum;
            }
        }
        
        // DP
        public int numTrees(int n) {
            int[] array = new int[n + 1];
            array[0] = 1;
            for (int i = 1; i <= n; i++) {
               for (int j = 1; j <= i; j++) {
                   array[i] += array[j - 1] * array[i - j];
               }
            }
            return array[n];
        }
    }
    

    Obviously, DP has a much better performance.
    The idea is simple.
    Make j as the root among i nodes
    Left sub-tree has j - 1 nodes
    Right sub-tree has i - j nodes;
    f(i, j) = f(j - 1) * f(i - j);
    f(i) = f(i, 1)+ f(i, 2) + .... + f(i, i);


  • 0
    A

    here is my solution:

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

Log in to reply
 

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