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

import java.util.*;

public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int n = matrix.length;//一维数组的长度 int m = matrix[0].length;//二维数组的长度 int[][] dp = new int[n][m];//创建一个二维dp数组 //初始化二维dp数组dp[0][0] dp[0][0] = matrix[0][0]; //初始化二维dp数组第一列 for(int i=1;i<n;i++){ dp[i][0] = dp[i-1][0] + matrix[i][0]; } //初始化二维dp数组第一行 for(int i=1;i<m;i++){ dp[0][i] = dp[0][i-1] + matrix[0][i]; } //遍历，使用动态规划求解，具有最优子结构， //递推关系式：dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j]; for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j]; } }

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

}