Construct a two-tree to solve the problem. very clear to understand.Beats 97.44%


  • 0
    M

    When I ponder the problem, The tow-tree structure is very suitable for the wok flow. Because we need to decide to move down or right at every point.
    I take the DFS as my strategy.
    code:

    public class Solution {
        public class TreeNode{  
            int down;  
            int right;  
            TreeNode(int down,int right){  
                this.down = down;  
                this.right = right;  
            }  
        }  
        public int minPathSum(int[][] grid) {
            
    	int m = grid.length;
    	if( m == 0 ) return 0;
    	int n = grid[0].length;
    	if( m == 1 && n == 1) return grid[0][0];
    
    	return goDeep(new TreeNode(m-1,n-1),0,0,grid);
        }
        public int goDeep(TreeNode node, int i, int j, int[][]nums){ 
     
            if(node.down ==0 && node.right ==0) return nums[i][j];
            int downSum = Integer.MAX_VALUE, rightSum = Integer.MAX_VALUE;
            if(node.down > 0) {  
                if(nums[i+1][j] >= 0) {  
                    downSum = goDeep(new TreeNode(node.down - 1, node.right), i + 1, j, nums);  
                    nums[i + 1][j] = -downSum;  
                }else downSum = -nums[i+1][j];  
      
            }  
            if(node.right > 0) {  
                if(nums[i][j+1] >= 0) {  
                    rightSum = goDeep(new TreeNode(node.down, node.right - 1), i, j + 1, nums);  
                    nums[i][j + 1] =  -rightSum;  
                }else rightSum = -nums[i][j+1];  
            }  
      
            int result = Math.min(downSum,rightSum) + nums[i][j];  
            
            return result;  
      
        } 
    }
    

    Besides, I feel very strange why the algorithm is so fast ? because I use the same idea to solve the 63th problem, it's not perfect.


Log in to reply
 

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