DP Solution


  • 0
    I
    public class Solution {
        public String optimalDivision(int[] nums) {
            float[][] buf = new float[nums.length][nums.length];
            String[][] expression = new String[nums.length][nums.length];
            //init
            for(int i=0; i < nums.length; i++) {
                buf[i][i] = nums[i];
                expression[i][i] = nums[i] + "";
                if(i<nums.length-1) {
                    buf[i][i+1] = nums[i]*1.0f/nums[i+1];
                    expression[i][i+1] = nums[i] + "/" + nums[i+1];
                    buf[i+1][i] = buf[i][i+1];
                    expression[i+1][i] = nums[i] + "/" + nums[i+1];
                }
            }
    
            //print(buf);
            //print(expression);
    
            for(int k = 2; k < nums.length; k ++) {
                for (int i = 0; i < nums.length - k; i++) {
                    int j = i + k;
                    //find min given i,j
                    float min  = Float.MAX_VALUE;
                    //find max given i,j
                    float max = Float.MIN_VALUE;
    
                    int pos = -1;
                    int pos2 = -1;
                    for (int m = i; m < j; m++) {
                        float tmp2 = buf[m][i] / buf[m + 1][j];
                        if (tmp2 < min) {
                            min = tmp2;
                            pos = m;
                        }
                        float tmp = buf[i][m] / buf[j][m + 1];
                        if (tmp > max) {
                            max = tmp;
                            pos2 = m;
                        }
                    }
                    buf[j][i] = min;
                    expression[j][i] = concat(expression[pos][i], expression[pos+1][j]);
    
                    buf[i][j] = max;
                    expression[i][j] = concat(expression[i][pos2], expression[j][pos2+1]);
    
                    //print(buf);
                    //print(expression);
                }
            }
            return expression[0][nums.length-1];
        }
        
        private String concat(String str1, String str2) {
            if(str2.indexOf('/') == -1) {
                return str1 + "/" + str2;
            }
            else {
                return str1 + "/(" + str2 + ")";
            }
        }
    }
    

Log in to reply
 

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