Java DFS+Cache


  • 0

    all credits from https://leetcode.com/articles/optimal-division/

    public class Solution {
        ResultType[][] cache;
        public String optimalDivision(int[] nums) {
            if (nums == null || nums.length == 0) return "";
            cache = new ResultType[nums.length][nums.length];
            ResultType rs = search(nums, 0, nums.length - 1);
            return rs.maxPath;
        }
        
        private ResultType search(int[] A, int start, int end) {
            ResultType rs = new ResultType();
            if (start == end) {
                rs.minVal = rs.maxVal = A[start];
                rs.minPath = rs.maxPath = A[start] + "";
                return rs;
            }
            if (cache[start][end] != null) return cache[start][end];
            
            double min = Double.MAX_VALUE, max = -1;
            String minPath = "", maxPath = "";
            for (int i = start; i < end; i++) {
                ResultType left = search(A, start, i);
                ResultType right = search(A, i + 1, end);
                if (min > left.minVal / right.maxVal) {
                    min = left.minVal / right.maxVal;
                    rs.minPath = left.minPath + "/" + (i + 1 == end ? right.maxPath : "(" + right.maxPath + ")");
                    rs.minVal = min;
                } 
                if (max < left.maxVal / right.minVal) {
                    max = left.maxVal / right.minVal;
                    rs.maxPath = left.maxPath + "/" + (i + 1 == end ? right.minPath : "(" + right.minPath + ")");
                    rs.maxVal = max;
                }
            }
            cache[start][end] = rs;
            return rs;
        }
        
        class ResultType {
            double minVal, maxVal;
            String minPath, maxPath;
        }
    }
    

Log in to reply
 

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