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

/*动态规划  矩阵大小MxN
    遍历了，时间复杂度O(MxN)
    dp大小int [M][N]，空间复杂度O(MxN)
    * */
    public static int minPathSum1(int[][]m){
        if(m==null||m.length==0||m[0].length==0||m[0]==null){
            return 0;
        }
        int row=m.length;       //行
        int col=m[0].length;    //列
        int[][]dp=new int[row][col];

        //起点
        dp[0][0]=m[0][0];
        //第一行
        for (int i = 1; i <col ; i++) {
            dp[0][i]=dp[0][i-1]+m[0][i];
        }
        //第一列
        for (int i = 1; i <row ; i++) {
            dp[i][0]=dp[i-1][0]+m[i][0];
        }

        for (int i = 1; i <row ; i++) {
            for (int j = 1; j <col ; j++) {
                dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+m[i][j];
            }
        }

        return dp[row-1][col-1];
    }


    //时间复杂度不变，空间复杂度O(min{M,N})
    public static int minPathSum2(int[][]m) {
        if (m == null || m.length == 0 || m[0].length == 0 || m[0] == null) {
            return 0;
        }
        int more=Math.max(m.length,m[0].length);    //行数与列数中较大的
        int less=Math.min(m.length,m[0].length);    //行数与列数中较小的
        boolean rowmore= m.length==more;        //true：行数较大
        int[]arr=new int[less];
        arr[0]=m[0][0];
        for (int i = 1; i < less; i++) {
            arr[i]=arr[i-1]+(rowmore?m[0][i]:m[i][0]);
        }

        for (int i = 1; i <more ; i++) {
            //换行更新
            arr[0]=arr[0]+(rowmore?m[i][0]:m[0][i]);
            for (int j = 1; j <less ; j++) {
                arr[j]= Math.min(arr[j-1],arr[j]) + (rowmore?m[i][j]:m[j][i]);
            }
        }

        return arr[less-1];
    }


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j = 0;j<m;j++){
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(minPathSum1(arr));
    }