java with space O(n)


  • 0
    5

    public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
    if(triangle==null){
    return 0;
    }
    int size=triangle.size();
    for(int i=1;i<size;i++){
    int newElement=triangle.get(i-1).get(0)+triangle.get(i).get(0);
    triangle.get(i).set(0,newElement);
    }
    for(int j=1;j<size;j++){
    int newElement=triangle.get(j-1).get(j-1)+triangle.get(j).get(j);
    triangle.get(j).set(j,newElement);
    }
    for(int i=2;i<size;i++){
    for(int j=1;j<i;j++){
    int newElement=Math.min(triangle.get(i-1).get(j),triangle.get(i-1).get(j-1))+triangle.get(i).get(j);
    triangle.get(i).set(j,newElement);
    }
    }
    Collections.sort(triangle.get(size-1));
    return triangle.get(size-1).get(0);
    }
    }


Log in to reply
 

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