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

import java.util.*;


public class Solution {
    //1.以第dp[i][j]结尾的最小路径和。
    public static int minPathSum (int[][] matrix) {
        // write code here
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        //1,初始化 要保证dp数组的第一列和第一行填表时满足逻辑
        dp[0][0] = matrix[0][0];
        //处理第一行
        for(int i=1;i<n;i++){
            //前一个加当前值
            dp[0][i] = matrix[0][i] +dp[0][i-1];
        }
        //处理第一列
        for(int j=1;j<m;j++){
            //上一个加当前值
            dp[j][0] =matrix[j][0] +dp[j-1][0];
        }

        //2.填表
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //取两种情况最小值,注意映射关系
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j];

            }
        }

        return dp[m-1][n-1];
    }
}