JAVA DP solution


  • -1
    S
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0)
            return 0;
        if (triangle.size() == 1)
            return triangle.get(0).get(0);
            
        List<Integer> top, bottom;
        int min, res = Integer.MAX_VALUE;
        
        for (int i = 1; i < triangle.size(); i++) {
            top = triangle.get(i-1);
            bottom = triangle.get(i);
            
            for (int j = 0; j < bottom.size(); j++) {
                if (j == 0)
                    min = top.get(j);
                else if (j == bottom.size() - 1)
                    min = top.get(j-1);
                else
                    min = Math.min(top.get(j-1), top.get(j));
                
                if (i == triangle.size() - 1) {
                    if (res > min + bottom.get(j))
                        res = min + bottom.get(j);
                }
                    
                bottom.set(j, min + bottom.get(j));
            }
        }
    
        return res;
    }

Log in to reply
 

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