How about a backtracking O(n^2) solution like this?


  • 0

    This solution passed 42 tests out of 43, except the last one with a huge test data set with a time limited exception. However, the average time complexity for this solution is still O(N^2), same as DP solution.

    Has any one tried backtracking for this question?

    Thanks!

    class Solution {
        private int min = Integer.MAX_VALUE;
        
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0) return 0;
            helper(0, triangle, 0, 0);
            return min;
        }
        
        private void helper(int cur, List<List<Integer>> triangle, int level, int i) {
            if (level == triangle.size()) {
                min = Math.min(cur, min);
                return;
            }
            
            int a = triangle.get(level).get(i);
            helper(cur + a, triangle, level+1, i);
            
            if (i < level) {
                int b = triangle.get(level).get(i+1);
                helper(cur + b, triangle, level+1, i+1);    
            }
        }
    }
    

Log in to reply
 

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