Dfs + memory search. (4ms)


  • 2
    L

    Algo: dfs + memory search

    The following code is for your reference. But there are still a lot of improvement we can do. Like, integer overflow, private data member, ...
    How many ones can you find out? :)

    class Solution {
    public:
        int numTrees(int n) {
    		if (n <= 1)
    			return 1;
    		if (dic.find(n) != dic.end())
    			return dic[n];
    		int ans = 0;
    		for (int i = 0; i < n; ++i) {
    			int left = i;
    			int right = n - i - 1;
    			ans += numTrees(left) * numTrees(right);
    		}
    		return dic[n] = ans;
        }
    	unordered_map<int, int> dic;
    };

Log in to reply
 

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