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

思路：构建dp，每一个位置记录走过的路径和，最后返回右下角即可。
可以将matrix.length 和 matrix[0].length 提出来 赋入新变量中，这样可读性会更高。

public int minPathSum (int[][] matrix) {
        // write code here
        //构建dp数组，这里存的是路线累计的值，而不是个别位置的数字
        int [][]dp=new int[matrix.length][matrix[0].length];

        dp[0][0]=matrix[0][0];    //赋开头
        //构建第一行、第一列的dp
        for(int i=1;i<matrix[0].length;i++) dp[0][i]=dp[0][i-1]+matrix[0][i];   //第一行
        for(int j=1;j<matrix.length;j++) dp[j][0]=dp[j-1][0]+matrix[j][0];   //第一列

        //开始dp构建,从下标(1,1)开始，一行一行遍历,想要到达下一个对角线，就要进行判断哪个最小
        for(int i=1;i<matrix.length;i++)
            for(int j=1;j<matrix[0].length;j++) 
                dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+matrix[i][j];   

        return dp[matrix.length-1][matrix[0].length-1];



    }