8 lines O(n) space, O(n^2) time Java solution beats 71%


  • 2
    S
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] cache = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> row = triangle.get(i);
            for (int j = 0; j < row.size(); j++) {
                cache[j] = row.get(j) + Math.min(cache[j], cache[j + 1]);
            }
        }
        return cache[0];
    }

Log in to reply
 

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