My AC Java Solution with inline space


  • 0
    S
    public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        
        int minsum = Integer.MAX_VALUE;
        int N = triangle.size();
        if(N==0) return 0;
        if(N==1) return triangle.get(0).get(0);
        for(int i =1; i <N;i++)
        {
            List<Integer> line = triangle.get(i);
            List<Integer> lastline = triangle.get(i-1);;
            for(int j = 0; j<line.size();j++)
            {
                int left = Integer.MAX_VALUE;
                int right = Integer.MAX_VALUE;
                //from upper left
                if(j-1>=0)
                {
                    left = lastline.get(j-1)+line.get(j);
                }
                //from upper right
                if(j<lastline.size())
                {
                    right = lastline.get(j)+line.get(j);
                }
                //pick the smaller and set it to j
                int min = Math.min(left, right);
                line.set(j,min);
            }
        }
        //the last line has all the sum and pick the min one
        for(int i:triangle.get(N-1))
        {
            minsum = Math.min(minsum, i);
        }
        
        return minsum;
        
    }
    

    }


Log in to reply
 

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