Simple Java Solution for Triangle


  • 0
    A
      public int minimumTotal(List<List<Integer>> triangle) {
            int max = Integer.MAX_VALUE;
            if(triangle == null||triangle.size()==0)return 0;
            int lon = triangle.get(triangle.size()-1).size();
            int dep = triangle.size();
            if(dep == 1)return triangle.get(0).get(0);
            if(dep == 2)return Math.min(triangle.get(0).get(0)+triangle.get(1).get(0),triangle.get(0).get(0)+triangle.get(1).get(1));
            int[][] m = new int[dep][lon];
            m[0][0] = triangle.get(0).get(0);
            m[1][0] = m[0][0] + triangle.get(1).get(0);
            m[1][1] = m[0][0] + triangle.get(1).get(1);
            for(int i = 2; i < triangle.size();i++){
                List<Integer> line = triangle.get(i);
                for(int j = 0; j < line.size(); j++){
                    if(j == 0){
                        m[i][j] = m[i-1][j]+line.get(j);
                        continue;
                        
                    };
                    if(j == line.size()-1){
                      m[i][j] = m[i-1][j-1]+line.get(j);
                      continue;
                    } 
                    m[i][j] = Math.min(m[i-1][j]+line.get(j),m[i-1][j-1]+line.get(j));
                }
            }
            for(int i = 0; i < lon; i++){
                if(m[dep-1][i] < max) max = m[dep-1][i];
            }
            return max;
        }
    

    Have fun :)


Log in to reply
 

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