Top-down java solution


  • 0
    U
    public int minimumTotal(List<List<Integer>> triangle) {
            int row = triangle.size();
            
            for (int i = 1; i < row; ++i) {		// traverse every row
            	triangle.get(i).set(0, triangle.get(i).get(0) + triangle.get(i - 1).get(0));		// first item
            	for (int idx = 1; idx < i; ++idx)												// items among them
            		triangle.get(i).set(idx, triangle.get(i).get(idx) + Math.min(triangle.get(i - 1).get(idx - 1), 
            				triangle.get(i - 1).get(idx)));
            	triangle.get(i).set(i, triangle.get(i).get(i) + triangle.get(i - 1).get(i - 1));	// last item
            }
            
            int min = Integer.MAX_VALUE;
            for (int i : triangle.get(row - 1))
            	min = (min > i) ? i : min;
            return min;
        }
    

Log in to reply
 

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