DP Solution which also works for positive float point numbers


  • 0
    F

    Since the numbers are positive integers, there is some shortcut. If the numbers are positive double/float numbers. Then only DP solution is available?

    public class Solution {
        
        private void postprocess(int[] nums, byte[][] ind, int s, int e, boolean findmin, boolean sndpart, StringBuilder res){
            if( s == e){ // obvious the fst part
                res.append(nums[s]);
            }else{
                if(sndpart){
                    res.append('(');
                }
                int div = findmin?ind[e][s]:ind[s][e];
                postprocess(nums, ind, s, div, findmin, false, res);
                res.append('/');
                postprocess(nums, ind, div + 1, e, !findmin, true, res);
                if(sndpart){
                    res.append(')');
                }
            }
        }
    
        public String optimalDivision(int[] nums) {
            int len = nums.length;
            double[][] max = new double[len][len];
            byte[][] ind = new byte[len][len];
            for(int i = 0; i < len; i++){
                max[i][i] = nums[i];
            }
            double mx, mi;
            for(int L = 1; L <= len - 1; L++){
                for(int s = 0; s < len - L; s++){
                    for(int j = s; j < s + L; j++){
                        mx = max[s][j]/max[s+L][j+1];
                        mi = max[j][s]/max[j+1][s+L];
                        if(mx > max[s][s+L]){
                            max[s][s+L] = mx;
                            ind[s][s+L] = (byte)j;
                        }
                        if(max[s+L][s] == 0.0 || mi < max[s+L][s]){
                            max[s+L][s] = mi;
                            ind[s+L][s] = (byte)j;
                        }
                    }
                }
            }
    
            StringBuilder res = new StringBuilder();
            postprocess(nums, ind, 0, nums.length - 1, false, false, res);
            return res.toString();
        }
    }
    

  • 0
    F

    Float point version with a simple test case which is more interesting:

    public class Solution {
    
        private void postprocess(double[] nums, byte[][] ind, int s, int e, boolean findmin, boolean sndpart, StringBuilder res){
            if( s == e){ // obvious the fst part
                res.append(nums[s]);
            }else{
                if(sndpart){
                    res.append('(');
                }
                int div = findmin?ind[e][s]:ind[s][e];
                postprocess(nums, ind, s, div, findmin, false, res);
                res.append('/');
                postprocess(nums, ind, div + 1, e, !findmin, true, res);
                if(sndpart){
                    res.append(')');
                }
            }
        }
    
        public String optimalDivision(double[] nums) {
            int len = nums.length;
            double[][] max = new double[len][len];
            byte[][] ind = new byte[len][len];
            for(int i = 0; i < len; i++){
                max[i][i] = nums[i];
            }
            double mx, mi;
            for(int L = 1; L <= len - 1; L++){
                for(int s = 0; s < len - L; s++){
                    for(int j = s; j < s + L; j++){
                        mx = max[s][j]/max[s+L][j+1];
                        mi = max[j][s]/max[j+1][s+L];
                        if(mx > max[s][s+L]){
                            max[s][s+L] = mx;
                            ind[s][s+L] = (byte)j;
                        }
                        if(max[s+L][s] == 0.0 || mi < max[s+L][s]){
                            max[s+L][s] = mi;
                            ind[s+L][s] = (byte)j;
                        }
                    }
                }
            }
    
            StringBuilder res = new StringBuilder();
            postprocess(nums, ind, 0, nums.length - 1, false, false, res);
            return res.toString();
        }
    
        public static void main(String[] args){
            Solution sol = new Solution();
            System.out.println(sol.optimalDivision(new double[]{100, 10, 0.3, 5, 0.5})); \\ output 100.0/10.0/(0.3/(5.0/0.5))
        }
    }
    

Log in to reply
 

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