Accepted C Solution Rt O(n) Sp O(n) from top to bottom


  • 0
    R
    int minimumTotal(int **triangle, int numRows) {
    	if(0>=numRows) return 0;
    	int *res=malloc(sizeof(int)*numRows);
    	if(NULL==res)
    		exit(-1);
    	res[0]=triangle[0][0];
    
    	int i=1;
    	while(i<numRows){
    		int *cur=triangle[i];
    		//last one 
    		res[i]=res[i-1]+cur[i];
    		int j=i-1;
    		while(j>0){
    			res[j]=(res[j]<res[j-1])?res[j]:res[j-1];
    			res[j]+=cur[j];
    			--j;
    		}
    		//first one
    		res[0]+=cur[0];
    		++i;
    	}
    
    	int ret=res[0];
    	i=1;
    	while(i<numRows){
    		if(ret>res[i])
    			ret=res[i];
    		++i;
    	}
    	free(res);
    	return ret;
    }
    

    the idea is to calculate the minimum path to the current node of current row from the top. when reach the bottom,it's easy to find which node has the smallest path sum.


Log in to reply
 

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