给定一个由非负整数填充的m x n的二维数组,现在要从二维数组的左上角走到右下角,请找出路径上的所有数字之和最小的路径。
注意:你每次只能向下或向右移动。
注意:你每次只能向下或向右移动。
public int minPathSum (int[][] grid) { // write code here int row=grid.length; int col=grid[0].length; return f(grid, row-1, col-1); } // 递归算法 public static int f(int[][] grid, int i, int j){ // 找好base if(i==0 && j>0) { return f(grid, 0,j-1) + grid[0][j]; } if(j==0 && i>0){ return f(grid, i-1, 0) + grid[i][0]; } if(i==0 && j==0){ return grid[0][0]; } return Math.min(f(grid, i-1, j)+grid[i][j], f(grid, i, j-1)+grid[i][j]); }
// 清清爽爽动态规划 public class Solution { public int minPathSum (int[][] grid) { int m = grid.length, n = grid[0].length; int left = Integer.MAX_VALUE, up = Integer.MAX_VALUE; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) continue; if (i >= 1) up = grid[i-1][j]; if (j >= 1) left = grid[i][j-1]; grid[i][j] += Math.min(up, left); } } return grid[m-1][n-1]; } }
public class Solution{ //先对最左一列和最上一行特殊处理,因为这样的一列和一行中每个元素的来路只有一条,它是固定的。 //然后剩下的内层的矩形框中,每个元素的来路可能来自于左面元素,也有可能来自于上面元素。再加上 //当前元素值就是走到该位置经历的路径最小和 public int minPathSum(int[][] grid) { int m=grid.length; int n=grid[0].length; if(m==0||n==0){ return 0; } int[][] minimumPathSum=new int[m][n]; minimumPathSum[0][0]=grid[0][0]; for (int i=1;i<m;i++){ minimumPathSum[i][0]=grid[i][0]+minimumPathSum[i-1][0]; }//lie for (int j=1;j<n;j++){ minimumPathSum[0][j]=grid[0][j]+minimumPathSum[0][j-1]; } for (int i=1;i<m;i++){ for (int j=1;j<n;j++){ minimumPathSum[i][j]=Math.min(minimumPathSum[i][j-1],minimumPathSum[i-1][j])+grid[i][j]; } } return minimumPathSum[m-1][n-1]; } }
public class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; int[][] dp = new int[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (i == 0 && j == 0) { dp[i][j] = grid[i][j]; } else if (i == 0) { dp[i][j] = dp[i][j - 1] + grid[i][j]; } else if (j == 0) { dp[i][j] = dp[i - 1][j] + grid[i][j]; } else { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } } return dp[rows - 1][cols - 1]; } }
public int minPathSum(int[][] grid) { int m=grid.length,n=grid[0].length; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0&&j!=0)grid[i][j]+=grid[i][j-1]; else if(i!=0&&j==0)grid[i][j]+=grid[i-1][j]; else if(i!=0&&j!=0)grid[i][j]+=Math.min(grid[i-1][j], grid[i][j-1]); } } return grid[m-1][n-1]; } 现在觉得medium dp有点**
public class Solution { public int minPathSum(int[][] grid) { int m =grid.length; int n = grid[0].length; if(grid==null || m==0 || n==0) return 0; int[][]res = new int[m][n]; res[0][0] = grid[0][0]; for(int i = 1;i<n;i++){ res[0][i] = res[0][i-1]+grid[0][i]; } for(int i = 1;i<m;i++){ res[i][0] = res[i-1][0]+grid[i][0]; } for(int i = 1;i<m;i++){ for(int j=1;j<n;j++){ res[i][j] = Math.min(res[i-1][j],res[i][j-1])+grid[i][j]; } } return res[m-1][n-1]; } }
import java.util.Arrays; public class Solution { public int minPathSum(int[][] grid) { if (grid == null) { return 0; } int rowLen = grid.length; int colLen = grid[0].length; int[] res = new int[colLen + 1]; Arrays.fill(res, Integer.MAX_VALUE); res[1] = 0; for (int i = 1; i <= rowLen; i++) { for (int j = 1; j <= colLen; j++) { //当前点的最小路径和为 : 从左边和上边选择最小的路径和再加上当前点的值 //res[j]没更新之前就表示i-1行到第j个元素的最小路径和 //因为是从左往右更新,res[j-1]表示i行第j-1个元素的最小路径和 res[j] = Math.min(res[j], res[j - 1]) + grid[i - 1][j - 1]; } } return res[colLen]; } }
public class Solution { public int minPathSum(int[][] grid) { if(grid == null || grid.length < 1) return 0; int m = grid.length; int n = grid[0].length; int[] dp = new int[n]; dp[0] = grid[0][0]; for(int i=1; i<n; i++) dp[i] = dp[i-1] + grid[0][i]; for(int i=1; i<m; i++) for(int j=0; j<n; j++) { if(j == 0) { dp[j] += grid[i][j]; } else { dp[j] = Math.min(grid[i][j]+dp[j],grid[i][j]+dp[j-1]); } } return dp[n-1]; } }
public int minPathSum(int[][] grid) { int m = grid.length;// row int n = grid[0].length; // column for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j != 0) { grid[i][j] = grid[i][j] + grid[i][j - 1]; } else if (i != 0 && j == 0) { grid[i][j] = grid[i][j] + grid[i - 1][j]; } else if (i == 0 && j == 0) { grid[i][j] = grid[i][j]; } else { grid[i][j] = Math.min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j]; } } } return grid[m - 1][n - 1]; }
public class Solution { public int minPathSum(int[][] grid) { for (int i = 1; i < grid.length; i ++ ) { grid[i][0] += grid[i - 1][0]; } for (int i = 1; i < grid[0].length; i ++ ) { grid[0][i] += grid[0][i - 1]; } for (int i = 1; i < grid.length; i ++ ) { for (int j = 1; j < grid[0].length; j ++ ) { grid[i][j] += grid[i - 1][j] > grid[i][j - 1] ? grid[i][j - 1] : grid[i - 1][j]; } } return grid[grid.length - 1][grid[0].length - 1]; } }