Java divide&conquer solution - beat 94%


  • 0
    D
    class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int[][] hash = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
            for (int[] row : hash) {
                Arrays.fill(row, Integer.MAX_VALUE);
            }
            return dc(0,0,triangle,hash);
        }
        
        public int dc(int x, int y, List<List<Integer>> triangle,int[][] hash) {
            if (x == triangle.size()) return 0;
            if (hash[x][y] != Integer.MAX_VALUE) return hash[x][y];
            int left = dc(x+1, y, triangle, hash);
            int right = dc(x+1, y+1, triangle, hash);
            hash[x][y] = triangle.get(x).get(y) + Math.min(left, right);
            return hash[x][y];
        }
    }
    

    If n is # of levels (height + 1), then time complexity is O(n^2).
    If you don't use hash to reduce repetitive computations, the time complexity will be O(2^n).


Log in to reply
 

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