My c code , 4ms , time O(n),space O(n)?


  • -4
    8
    int **t;
    int n;
    int *arr=NULL;
    
    int fun(int r,int c){
    	if(*(arr+r*n+c)) return *(arr+r*n+c);
    	int a=0x7fffffff,b=0x7fffffff;
    	if(c)
    		a = fun(r-1,c-1);
    	if(c < r)
    		b = fun(r-1,c);
    	if(!c&&!r)a=b=0;
    	return *(arr+r*n+c) = t[r][c]+(a<b?a:b);
    }
    
    int minimumTotal(int **triangle, int numRows) {
    	if(arr)
    		free(arr);
    	arr = (int *)malloc(numRows*numRows*sizeof(int));
    	int minv = 0x7fffffff;
    	t = triangle;
    	n = numRows;
    	memset(arr,0,numRows*numRows*sizeof(int));
    	for(int i = 0;i < numRows;i ++){
    		int t = fun(numRows-1,i);
    		if(t < minv)
    			minv = t;
    	}
    	return minv;
    	
    }

Log in to reply
 

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