AC DP solution O(n^2) ?


  • 0
    C

    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];
    		
    	}
    }
    

Log in to reply
 

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