题解 | #矩阵的最小路径和#
矩阵的最小路径和
http://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ ArrayList<Integer> path=new ArrayList<Integer>(); boolean visited[][]; int[][] minXY; public int minPathSum (int[][] matrix) { visited=new boolean[matrix.length][matrix[0].length]; minXY=new int[matrix.length][matrix[0].length]; for(int i=0;i<matrix.length;i++) { for(int j=0;j<matrix[0].length;j++) { minXY[i][j]=-1; } } return dfs(matrix,0,0); } int dfs(int[][] matrix,int x,int y ) { int right=20000,down=20000; path.add(matrix[x][y]); if(y+1<matrix[0].length && visited[x][y+1]!=true ) { right= minXY[x][y+1]!=-1 ? minXY[x][y+1] : dfs(matrix,x,y+1); } //down if(x+1<matrix.length && visited[x+1][y]!=true ) { down= minXY[x+1][y]!=-1 ? minXY[x+1][y] : dfs(matrix,x+1,y); } if(x==matrix.length-1 && y==matrix[0].length-1) { right=0;down=0; } //right visited[x][y]=false; path.remove(path.size()-1); minXY[x][y]=Math.min(matrix[x][y]+right,matrix[x][y]+down); return minXY[x][y]; } }