Java Top-Down(4ms) & Bottom-Up(6ms) Solution


  • 0
    L
    //Bottom-Up 6ms
    public class Solution {
        public int minimumTotal1(List<List<Integer>> triangle) {
            int[] nums = new int[triangle.size()];
            for(int i = 0; i < triangle.size(); i++)
                nums[i] = triangle.get(triangle.size() - 1).get(i);
            for(int i = triangle.size() - 2; i >= 0; i--){
                for(int j = 0; j < triangle.get(i).size(); j++){
                    nums[j] = triangle.get(i).get(j) + Math.min(nums[j], nums[j + 1]);
                }
            }
            return nums[0];
        }
    }
    
    //Top-Down 4ms
    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            if(triangle.size() == 0) return 0;
            long[][] cache = new long[triangle.size()][triangle.size()];
            for(int i = 0; i < cache.length; i++)
                for(int j = 0; j < cache.length; j++)
                    cache[i][j] = Long.MIN_VALUE;
            return dfs(triangle, 0, 0, 0, cache);
        }
        
        private int dfs(List<List<Integer>> triangle, int iCur, int jCur, int total, long[][] cache){
            int min = Integer.MAX_VALUE;
            if(cache[iCur][jCur] != Long.MIN_VALUE){
                min = (int)cache[iCur][jCur];
            }
            else if(iCur == triangle.size() - 1){
                min = triangle.get(iCur).get(jCur);
            }else{
                min = dfs(triangle, iCur + 1, jCur, triangle.get(iCur).get(jCur), cache);
                min = Math.min(min, dfs(triangle, iCur + 1, jCur + 1, triangle.get(iCur).get(jCur), cache));
            }
            cache[iCur][jCur] = min;
            return min + total;
        }
    
    }

Log in to reply
 

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