Java solution -- dynamic programming


  • 21
    P
    public int minimumTotal(List<List<Integer>> trgl) {
        int sz = trgl.size();
        int[] results = new int[sz+1];
        
        for(int i=sz-1; i>=0; i--) {
            List<Integer> tmp = trgl.get(i);
            
            for(int j=0; j<tmp.size(); j++) {
                results[j] = Math.min(results[j], results[j+1]) + tmp.get(j);
            }
        }
        return results[0];
    }

  • 0
    P

    Hi peng4,

    Your solution requires the tmp.size() be smaller than trgl.size(), if the triangle gets too fat, it will result ArrayIndexOutOfBoundsException. E.g., if the input is [[-10],[2,3,4,6]]


  • 0
    Y

    @pureblue That is an illegal input. every level of the triangle should only 1 number larger than its above level.


Log in to reply
 

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