题解 | #矩阵的最小路径和#

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