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

• 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.

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