C++ 0ms dp no recursion


  • 0
    R

    class Solution {

    public:

    int numTreesHelper(int n, int* a) 
    {
    	if((n == 0) || (n == 1))
    		return 1;
    	a[0] = 1;
    	a[1] = 1;
    	for(int i = 2; i <= n; i++)
    	{
    		for(int j = 0; j < i; j++)
    		{
    			a[i] += (a[j] * a[i - 1 - j]);
    		}
    	}
    	return a[n];
    }
    
    int numTrees(int n) {
        int* a = new int[n + 1];
    	memset(a, 0, (n + 1)* sizeof(int));
    	return numTreesHelper(n, a);
    }};

Log in to reply
 

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