DFS + Memorized Search


  • 0
    W
    public class Solution {
        public int numTrees(int n) {
            if (n <= 0) {
                return 0;
            }
            int []state = new int[n];//memorized search
            return helper(n, state);
            
        }
        public int helper(int n, int[] state) {
            if (n == 0) {
                return 1;
            }
            if (state[n - 1] != 0) {
                return state[n - 1];
            }
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += helper(i - 1, state) * helper(n - i, state);
            }
            state[n - 1] = sum;
            return sum;
        }
    

    }


Log in to reply
 

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