Simple C code in 1ms, DP, a little different from other solutions.


  • 1
    Y
    int solutions[1024]={1,1,};
    int calculated = 1;
    int numTrees(int n) {
        //f(n)=sum(i=0,i<n)[f(i)*f(n-i-1)]
        if(n<calculated)
            return solutions[n];
        int start = calculated+1;
        for(int loop = start;loop<n+1;loop++){
            int sum = 0;
            for(int i=0;i<loop;i++){
                sum += solutions[i]*solutions[loop-i-1];
            }
            solutions[loop]=sum;
        }
        calculated = n;
        return solutions[n];
    }
    

    The array solutions is declared as a global variable, that's reasonable.

    Assuming that this function will be called quite frequent, calculating solutions[2],solutions[3], ... ,solutions[i] will costs a lot time.

    For example, at the beginning, numTrees(10) is called.

    We will get solutions[0] to solutions[10], then return solutions[10], finished.

    Next time, numTrees(5) is called.

    If we didn't save the array solutions, we must calculate them again.

    If we saved the results in numTrees(10) as solutions[ ], we can return solutions[5] directly without any calculation.

    In my code, I use global variable.

    But obviously, static is a better way.

    static solutions[1024] = {1,1,};

    static calculated;


Log in to reply
 

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