Recursive Java solution with Dynamic Programming O(n^2) running time


  • -1
    T
    public class Solution {
        public int numTrees(int n) {
            Map<Integer, Integer> cache = new HashMap<>();
            cache.put(0,1);
            return numTrees(n, cache);
        }
        public int numTrees(int n, Map<Integer, Integer> cache) {
            if(cache.containsKey(n)) return cache.get(n);
            int count = 0;
            for(int i = 0; i < n; i++) {
                count += numTrees(i, cache) * numTrees(n - 1 - i, cache);
            }
            cache.put(n, count);
            return count;
        }
    }

Log in to reply
 

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