给定一个 n * m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。
数据范围:
,矩阵中任意值都满足 
要求:时间复杂度
例如:当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时,对应的返回值为12,
所选择的最小累加和路径如下图所示:
[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
12
[[1,2,3],[1,2,3]]
7
public int minPathSum (int[][] matrix) { int m =matrix[0].length; int n =matrix.length; int[][] dp = new int[m+1][n+1]; for(int i=1; i<m+1;i++){ for(int j=1; j<n+1;j++){ if(i==1||j==1){ dp[i][j] =dp[i-1][j]+dp[i][j-1] + matrix[i-1][j-1]; continue; } dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i-1][j-1]; } } return dp[m][n]; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here // 算法核心思想:记忆化搜索 // dp[i][j]表示当位置落在i,j上时,到n-1,m-1位置的最小路径和 // 初始化-1 int[][] dp = new int[matrix.length][matrix[0].length]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[0].length; j++) { dp[i][j] = -1; } } return process(matrix, 0, 0, dp); } public int process (int[][] matrix, int i, int j, int[][] dp) { int m = matrix.length; int n = matrix[0].length; // 递归出口 if (i == m - 1 && j == n - 1) { dp[i][j] = matrix[i][j]; return dp[i][j]; } // 递归分支 if (dp[i][j] != -1) { return dp[i][j]; } // 往下走 // 若不能往下走,则d也不影响Math.min(d, r)的取值 int d = Integer.MAX_VALUE; if (i < m - 1) { // 不会越界,可以走 if (dp[i + 1][j] == -1) { dp[i + 1][j] = process(matrix, i + 1, j, dp); } // 本位值路径和 = 向下走之后的路径和 + 本位值路径值 d = dp[i + 1][j] + matrix[i][j]; } // 往右走 // 若不能往右走,则r也不影响Math.min(d, r)的取值 int r = Integer.MAX_VALUE; if (j < n - 1) { // 不会越界,可以走 if (dp[i][j + 1] == -1) { dp[i][j + 1] = process(matrix, i, j + 1, dp); } // 本位值路径和 = 向右走之后的路径和 + 本位值路径值 r = dp[i][j + 1] + matrix[i][j]; } // 本位置的走法,等于向右走的走法 + 向下走的走法 dp[i][j] = Math.min(d, r); return dp[i][j]; } }
public int minPathSum (int[][] matrix) { // write code here int m=matrix.length ,n=matrix[0].length; int[][] dp=new int[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0 && j==0){ dp[i][j]=matrix[i][j]; }else if(i==0){ dp[i][j]=matrix[i][j]+dp[i][j-1]; }else if(j==0){ dp[i][j]=matrix[i][j]+dp[i-1][j]; }else{ dp[i][j]=matrix[i][j]+Math.min(dp[i-1][j] ,dp[i][j-1]); } } } return dp[m-1][n-1]; }
public int minPathSum (int[][] matrix) { int m=matrix.length; int n=matrix[0].length; int[][] dp=new int[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0&&j==0){ dp[i][j]=matrix[i][j]; }else if(i==0){ dp[i][j]=matrix[i][j]+dp[i][j-1]; }else if(j==0){ dp[i][j]=matrix[i][j]+dp[i-1][j]; }else{ dp[i][j]=Math.min(dp[i-1][j]+matrix[i][j],dp[i][j-1]+matrix[i][j]); } } } return dp[m-1][n-1]; }
public class Solution { public int minPathSum (int[][] matrix) { int height = matrix.length; int width = matrix[0].length; // 从[0,0]到[i,j]的最小路径和 int[][] dp = new int[height][width]; dp[0][0] = matrix[0][0]; for (int i = 1; i < height; i++) { dp[i][0] = dp[i - 1][0] + matrix[i][0]; } for (int j = 1; j < width; j++) { dp[0][j] = dp[0][j - 1] + matrix[0][j]; } for (int i = 1; i < height; i++) { for (int j = 1; j < width; j++) { dp[i][j] = Math.min( // 从上边向下 dp[i - 1][j] + matrix[i][j], // 从左边向右 dp[i][j - 1] + matrix[i][j] ); } } return dp[height - 1][width - 1]; } }
public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // 行数 int i = matrix.length; // 列数 int j = matrix[0].length; // 初始化表格 int[][] table = new int[i][j]; // 首位单元格 = matrix[0][0] table[0][0] = matrix[0][0]; // 此步骤是初始化从起点 0, 0 开始,直着向右 或 直着向下的 每一步所需路径和 // 第一行表格的值,都等于 当前单元格的值 + 上一个单元格的值 for(int k = 1; k < i; k++) table[0][k] = matrix[0][k] + table[0][k - 1]; // 第一列表格的值,都等于 当前单元格的值 + 上一行单元格的值 for(int k = 1; k < j; k++) table[k][0] = matrix[k][0] + table[k - 1][0]; // 从1,1开始,每次填充的表格 = min(当前单元格 + 上一个单元格的值,当前单元格 + 左边单元格的值) 取最小路径和 for(int m = 1; m < i; m++){ for(int n = 1; n < j; n++){ table[m][n] = Math.min(matrix[m][n] + table[m - 1][n], matrix[m][n] + table[m][n - 1]); } } // 循环结束, 表格最后一个元素即为解 return table[i-1][j-1]; } }
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int rows = matrix.length, columns = matrix[0].length; int[][] dp = new int[rows][columns]; dp[0][0] = matrix[0][0]; for (int i = 1; i < rows; i++) dp[i][0] = dp[i-1][0] + matrix[i][0]; for (int j = 1; j < columns; j++) dp[0][j] = dp[0][j-1] + matrix[0][j]; for (int i = 1; i < rows; i++) { for (int j = 1; j < columns; j++) { dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j], dp[i][j-1]); } } return dp[rows-1][columns-1]; } }
int n = matrix[0].length;//行数 int m = matrix.length;//列数 //填充数据 int[][] len = new int[m][n]; //len = matrix; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) { len[0][0] = matrix[i][j]; } else if (i == 0) { len[i][j] = matrix[i][j] + len[i][j - 1]; } else if (j == 0) { len[i][j] = matrix[i][j] + len[i - 1][j]; } else { len[i][j] = Math.min(len[i][j - 1], len[i - 1][j]) + matrix[i][j]; } } } return len[m-1][n-1];
public int minPathSum (int[][] matrix) { // write code here int x = matrix.length; int y = matrix[0].length; int[][] cache = new int[x][y]; for(int i = x-1;i>=0;i--) { for(int j = y-1;j>=0;j--) { if(i == x-1 && j == y-1) { cache[x-1][y-1] = matrix[x-1][y-1]; } else if(i == x-1) {//最右一排,只算下方路径 cache[i][j] = cache[i][j+1] + matrix[i][j]; } else if(j == y-1) {//最下一排,只算右侧路径 cache[i][j] = cache[i+1][j] + matrix[i][j]; } else {// 需要比较有侧和下方哪个最小 int xPath = 0,yPath = 0; cache[i][j] = Math.min(cache[i+1][j] + matrix[i][j], cache[i][j+1] + matrix[i][j]); } } } return cache[0][0]; }
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int row=matrix.length; int col=matrix[0].length; int[][] dp=new int[row][col];//表示ij位置到右下的最小路径和 //初始化 dp[row-1][col-1]=matrix[row-1][col-1]; for(int j=col-2;j>=0;j--){ dp[row-1][j]=dp[row-1][j+1]+matrix[row-1][j]; } for(int i=row-2;i>=0;i--){ dp[i][col-1]=dp[i+1][col-1]+matrix[i][col-1]; } //转移 for(int i=row-2;i>=0;i--){ for(int j=col-2;j>=0;j--){ dp[i][j]=Math.min(dp[i][j+1],dp[i+1][j])+matrix[i][j]; } } //返回 return dp[0][0]; } }
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int m=matrix.length; int n=matrix[0].length; int[][] dp=new int[m][n]; int sum1=0; int sum2=0; for(int i=0;i<m;i++) { sum1+=matrix[i][0]; dp[i][0]=sum1; } for(int j=0;j<n;j++) { sum2+=matrix[0][j]; dp[0][j]=sum2; } 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]; } }
public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int m = matrix.length, n = matrix[0].length; int[][] dp = new int[m][n]; dp[0][0] = matrix[0][0]; for ( int i = 1; i < n; i++ ) dp[0][i] = dp[0][i-1] + matrix[0][i]; for ( int i = 1; i < m; i++ ) dp[i][0] = dp[i-1][0] + matrix[i][0]; 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]; } }
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } // write code here int[][] dp = new int[matrix.length + 1][matrix[0].length + 1]; for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[i].length; j++) { if (i == 1) { dp[i][j] = dp[i][j - 1] + matrix[i - 1][j - 1]; } else if (j == 1) { dp[i][j] = dp[i - 1][j] + matrix[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i - 1][j - 1]; } } } return dp[matrix.length][matrix[0].length]; } }
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int row = matrix.length; int col = matrix[0].length; int[][] dp = new int[row][col]; dp[0][0] = matrix[0][0]; //处理第一行 for(int i = 1;i<col;i++){ dp[0][i] = dp[0][i-1] + matrix[0][i]; } //处理第一列 for(int i = 1;i<col;i++){ dp[i][0] = dp[i-1][0] + matrix[i][0]; } //动态计算 for(int i = 1; i < col;i++){ for(int j = 1; j < row ; j++){ dp[j][i] = matrix[j][i] + Math.min(dp[j][i-1],dp[j-1][i]); } } return dp[row-1][col-1]; } }
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here if(matrix==null) return 0; int height = matrix.length; int width = matrix[0].length; for(int i = 1; i<height; i++) { matrix[i][0] += matrix[i-1][0]; } for(int j = 1; j<width ; j++) { matrix[0][j] += matrix[0][j-1]; } for(int i = 1; i<height; i++) { for(int j = 1; j<width; j++) { matrix[i][j] += Math.min(matrix[i-1][j], matrix[i][j-1]); } } return matrix[height-1][width-1]; } }
二维dp
import java.util.*; public class Solution { public int minPathSum (int[][] matrix) { if (null == matrix) { return 0; } int m = matrix.length; int n = matrix[0].length; // 二维dp int[][] dp = new int[m + 1][n + 1]; // 初始化 for (int[] num : dp) { Arrays.fill(num, Integer.MAX_VALUE); } // 这里方便计算第一个值 dp[0][1] = dp[1][0] = 0; // 遍历矩阵 for (int i = 1;i <= matrix.length;i++) { for (int j = 1;j <= matrix[0].length;j++) { // 取左边和上面的较小值再累加 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i - 1][j - 1]; } } return dp[m][n]; } }
一维dp
import java.util.*; public class Solution { public int minPathSum (int[][] matrix) { if (null == matrix) { return 0; } int m = matrix.length; int n = matrix[0].length; // 一维dp int[] dp = new int[n + 1]; // 初始化 Arrays.fill(dp, Integer.MAX_VALUE); // 这里方便计算第一个值 //dp[0] = 0; // 遍历矩阵 for (int i = 1;i <= matrix.length;i++) { for (int j = 1;j <= matrix[0].length;j++) { if (i == 1 && j == 1) { // 第一个元素特殊处理 dp[j] = matrix[0][0]; } else { // 取左边和上面的较小值再累加 dp[j] = Math.min(dp[j], dp[j - 1]) + matrix[i - 1][j - 1]; } } } return dp[n]; } }
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int m=matrix.length; int n=matrix[0].length; for(int i=1;i<m;i++){ matrix[i][0]+=matrix[i-1][0]; } for(int j=1;j<n;j++){ matrix[0][j]+=matrix[0][j-1]; } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ matrix[i][j]+=Math.min(matrix[i-1][j],matrix[i][j-1]); } } return matrix[m-1][n-1]; } }