给定一个 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) { // 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]; } }
public int minPathSum (int[][] matrix) { int m=matrix.length; int n=matrix[0].length; int[][] dp = new int[m][n]; // dp[m-1][n-1]=matrix[m-1][n-1]; for (int i = m-2; i >=0; i--) { dp[i][n - 1] = dp[i+1][n-1]+matrix[i][n - 1]; } for (int i = n-2; i >=0; i--) { dp[m - 1][i] =dp[m-1][i+1]+matrix[m - 1][i] ; } for (int i = n - 2; i >= 0; i--) { for (int j = m-2; j >=0 ; j--) { dp[j][i] =matrix[j][i]+Math.min(dp[j+1][i] , dp[j][i + 1]) ; } } return dp[0][0]; }
private int minSum = Integer.MAX_VALUE; public int minPathSum (int[][] matrix) { dfs(0,0,matrix.length-1,matrix[0].length-1,0,matrix); return minSum; } private void dfs(int r,int c,int rLeft,int cLeft,int sum,int[][] matrix) { sum+=matrix[r][c]; if (rLeft==0 && cLeft==0) { minSum = Math.min(sum,minSum); return; } if (rLeft>0) dfs(r+1,c,rLeft-1,cLeft,sum,matrix); if (cLeft>0) dfs(r,c+1,rLeft,cLeft-1,sum,matrix); }
private int minSum = Integer.MAX_VALUE; public int minPathSum (int[][] matrix) { // 记录之前走到当前位置的最小值 int[][] memo = new int[matrix.length][matrix[0].length]; for (int i = 0; i < memo.length; i++) { for (int j = 0; j < memo[0].length; j++) { memo[i][j]=-1; } } dfs(0,0,matrix.length-1,matrix[0].length-1,0,matrix,memo); return minSum; } private void dfs(int r,int c,int rLeft,int cLeft,int sum,int[][] matrix,int[][] memo) { sum+=matrix[r][c]; if (memo[r][c]==-1) { memo[r][c]=sum; } // 大于之前某次的走法,排除以减小递归 if (sum>memo[r][c]) return; if (rLeft==0 && cLeft==0) { minSum = Math.min(sum,minSum); return; } if (rLeft>0) dfs(r+1,c,rLeft-1,cLeft,sum,matrix,memo); if (cLeft>0) dfs(r,c+1,rLeft,cLeft-1,sum,matrix,memo); }
public int minPathSum (int[][] matrix) { int R = matrix.length; int C = matrix[0].length; if (matrix==null || R*C==0) return 0; int[][] dp = new int[R][C]; for (int i = 0; i < C; i++) { if (i==0) dp[0][i]=matrix[0][i]; else dp[0][i]=matrix[0][i]+dp[0][i-1]; } for (int i = 0; i < R; i++) { if (i==0) dp[i][0]=matrix[i][0]; else dp[i][0]=matrix[i][0]+dp[i-1][0]; } for (int i = 1; i < R; i++) { for (int j = 1; j < C; j++) { dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j]; } } //for (int i = 0; i < R; i++) { // System.out.println(Arrays.toString(dp[i])); //} return dp[R-1][C-1]; }