# Java Backtrack Solution using DP 13ms

• ``````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;
}
}``````

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