Bottom Up Java solution with O(n) space


  • 0
    N
    public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null) {
            return 0;
        }
        int len = triangle.size();
        int [] cache = new int [len];
        List<Integer> lastRow = triangle.get(len-1);
        for(int i=0; i<lastRow.size(); i++) {
            cache[i] = lastRow.get(i);
        }
        for(int i=len-2; i>=0; i--) {
            List<Integer> list = triangle.get(i);
            for(int j=0; j<list.size(); j++) {
                cache[j] = Math.min(cache[j], cache[j+1]) + list.get(j);
            }
        }
        return cache[0];
      }
    }

Log in to reply
 

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