Java DP solution with O(1) space


  • 1
    T
    public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0) return 0;
        
        int size = triangle.size();
        
        for(int i = 1; i<size; i++){
            int i0 = triangle.get(i).get(0) + triangle.get(i-1).get(0);
            triangle.get(i).set(0, i0);
            
            int ilast = triangle.get(i).get(i) + triangle.get(i-1).get(i-1);
            triangle.get(i).set(i,ilast);
            
            for(int j = 1; j<i; j++){
                int sum = triangle.get(i).get(j) + Math.min(triangle.get(i-1).get(j-1), triangle.get(i-1).get(j));
                triangle.get(i).set(j,sum);
            }
        }
        
        //get the min of last level nodes
        int min = Integer.MAX_VALUE;
        for(int i = 0; i<size; i++){
            int a = triangle.get(size-1).get(i);
            min = Math.min(a, min);
        }
        return min;
    }
    }

  • 0
    T

    I did the exact same thing. It's cheating though since we modified the input list which may not be allowed in an interview setting.


  • 0
    E

    why not? Interviewers are not robots, they just want to know how you solve the problem.


Log in to reply
 

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