My code O(n) SPACE. backtracking!


  • 0
    public class Solution {
        int[] table;
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null) {
                return 0;
            }
            table = new int[triangle.size()];
            Arrays.fill(table, Integer.MIN_VALUE);
            return bt(triangle, 0, 0);
        }
        
        
        public int bt(List<List<Integer>> triangle, int row, int col) {
            if (row == triangle.size()) {
                return 0;
            }
            int curr = triangle.get(row).get(col);
            int left = 0;
            if (table[row] != Integer.MIN_VALUE) {
                left = table[row];
            } else {
                left = bt(triangle, row + 1, col);
            }
            int right = bt(triangle, row + 1, col + 1);
            table[row] = right;
            return Math.min(left, right) + curr;
        }
    }
    

Log in to reply
 

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