# DP Solution

• 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 + ")";
}
}
}

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