Java Backtrack Solution using DP 13ms


  • 1
    public class Solution {
        
        class Tuple {
            String s;
            double v;
            public Tuple(String _s, double _v) {
                s = _s;
                v = _v;
            }
        }
        
        Tuple[][][] mem;
        
        public Tuple helper(int[] nums, int i, int j, boolean isMax) {
            if(i==j)
                return new Tuple(""+nums[i], 1.0*nums[i]);
            if(mem[i][j][isMax?0:1]!=null)
                return mem[i][j][isMax?0:1];
            if(isMax) {
                Tuple maxT = new Tuple("",0);
                for(int k=i; k<j; k++) {
                    Tuple t1 = helper(nums, i, k, true);
                    Tuple t2 = helper(nums, k+1, j, false);
                    if(t1.v/t2.v > maxT.v) {
                        maxT.v = t1.v/t2.v;
                        maxT.s = t1.s + (k+1==j ? ("/" + t2.s) : ("/(" + t2.s + ")"));
                    }
                }
                mem[i][j][0] = maxT;
                return maxT;
            } else {
                Tuple minT = new Tuple("",Double.MAX_VALUE);
                for(int k=i; k<j; k++) {
                    Tuple t1 = helper(nums, i, k, false);
                    Tuple t2 = helper(nums, k+1, j, true);
                    if(t1.v/t2.v < minT.v) {
                        minT.v = t1.v/t2.v;
                        minT.s = t1.s + (k+1==j ? ("/" + t2.s) : ("/(" + t2.s + ")"));
                    }
                }
                mem[i][j][1] = minT;
                return minT;
            }
        }
        
        public String optimalDivision(int[] nums) {
            mem = new Tuple[nums.length][nums.length][2];
            return helper(nums, 0, nums.length-1, true).s;
        }
    }

Log in to reply
 

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