# AC DP solution O(n^2) ?

• This is my DP solution. The main idea is: except the last slot (eg. gird[0][nums.length - 1] find Max)) find MIN between nums[row] / grid[row + 1][col] AND grid[row][col - 1] / nums[col]. It's better to draw the grid out first.

``````public class Solution {
public String optimalDivision(int[] nums) {
if (nums.length == 1) {
return String.valueOf(nums[0]);
}

if (nums.length == 2) {
return "" + nums[0] +"/" + nums[1];
}

String[][] s_grid = new String[nums.length][nums.length];
double[][] d_grid = new double[nums.length][nums.length];

for (int row = nums.length - 2; row >= 0; row--) {
for (int col = row + 1; col < nums.length; col++) {
if (col == row + 1) {
d_grid[row][col] = nums[row]/nums[col];
s_grid[row][col] = "" + nums[row] + "/" + nums[col];
} else {
if (row == 0 && col == nums.length - 1) {
//get max at last slot
if (nums[row] / d_grid[row + 1][col] >= d_grid[row][col - 1] / nums[col]) {
d_grid[row][col] = nums[row] / d_grid[row + 1][col];
s_grid[row][col] = "" +nums[row] +  "/(" + s_grid[row + 1][col] + ")";
} else {
d_grid[row][col] = d_grid[row][col - 1] / nums[col];
s_grid[row][col] = "" + nums[row] + "/" + s_grid[row + 1][col];
}

} else {
//get min except last slot
if (nums[row] / d_grid[row + 1][col] < d_grid[row][col - 1] / nums[col]) {
d_grid[row][col] = nums[row] / d_grid[row + 1][col];
s_grid[row][col] = "" +nums[row] +  "/(" + s_grid[row + 1][col] + ")";
} else {
d_grid[row][col] = d_grid[row][col - 1] / nums[col];
s_grid[row][col] = "" + nums[row] + "/" + s_grid[row + 1][col];
}
}
}
}
}

return s_grid[0][nums.length - 1];

}
}
``````

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