Simple Recursive solution with Cache


  • 0
    B

    public class Solution {
    IDictionary<int, int> dic = new Dictionary<int, int>();
    public int NumTrees(int n) {
    if(n == 0 || n == 1) return 1;

        if(dic.ContainsKey(n)){
            return dic[n];
        }
        
        var count = 0;
        for(int i = 0; i < n; i++){
            var left = NumTrees(i);
            var right = NumTrees(n - i - 1);
            
            count += left * right;
        }
        
        dic[n] = count;
        
        return count;
    }
    

    }


Log in to reply
 

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