My accepted Java solution, easy to understand !


  • 0
    W

    public class Solution{

      publicint minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null) return 0;
        
        int len = triangle.size();
        int[] values = new int[len];  //only O(n) extra space
        
        values[0] = triangle.get(0).get(0);
        for(int i=1; i<len; i++){
        	List<Integer> cur = triangle.get(i);
        	
        	for(int j=cur.size()-1; j>=0; j--){
        		if(j == 0){
        			values[j] = values[j] + cur.get(j);
        		}else if(j == cur.size()-1){
        			values[j] = values[j-1] + cur.get(j);
        		}else{
        			values[j] = (values[j] > values[j-1]? values[j-1]:values[j]) + cur.get(j);
        		}
        	}
        }
        
        Arrays.sort(values);
        	
        return values[0];
    }
    

    }


  • 0
    S

    Mine is almost the same except the last step. I use for loop to find the min value rather than sort(). I think sort takes O(nlogn) which is longer than for loop.


Log in to reply
 

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