给定一个由非负整数填充的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]);
}
发表于 2021-11-04 22:05:23
回复(0)
// 清清爽爽动态规划
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];
}
}
发表于 2021-08-09 11:18:19
回复(0)
public class Solution {
/**
*
* @param grid int整型二维数组
* @return int整型
* f(x, y) = min(f(x, y-1), f(x-1, y)) + map(x, y);
* f(0, 0) = map(0, 0);
*/
public int minPathSum (int[][] grid) {
// write code here
int[][] recode = new int[grid.length][grid[0].length];
for(int x=0; x<grid.length; x++) {
for(int y=0; y<grid[0].length; y++) {
recode[x][y] = grid[x][y];
if(x-1<0 && y-1>=0) {
recode[x][y] = grid[x][y] + recode[x][y-1];
}
if(x-1>=0 && y-1<0) {
recode[x][y] = grid[x][y] + recode[x-1][y];
}
if(x-1>=0 && y-1>=0) {
recode[x][y] = grid[x][y] + Math.min(recode[x][y-1], recode[x-1][y]);
}
}
}
return recode[grid.length-1][grid[0].length-1];
}
}
/**
*
* @param grid int整型二维数组
* @return int整型
* f(x, y) = min(f(x, y-1), f(x-1, y)) + map(x, y);
* f(0, 0) = map(0, 0);
*/
public int minPathSum (int[][] grid) {
// write code here
int[][] recode = new int[grid.length][grid[0].length];
for(int x=0; x<grid.length; x++) {
for(int y=0; y<grid[0].length; y++) {
recode[x][y] = grid[x][y];
if(x-1<0 && y-1>=0) {
recode[x][y] = grid[x][y] + recode[x][y-1];
}
if(x-1>=0 && y-1<0) {
recode[x][y] = grid[x][y] + recode[x-1][y];
}
if(x-1>=0 && y-1>=0) {
recode[x][y] = grid[x][y] + Math.min(recode[x][y-1], recode[x-1][y]);
}
}
}
return recode[grid.length-1][grid[0].length-1];
}
}
编辑于 2020-07-13 20:37:56
回复(0)
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];
}
}
发表于 2020-04-26 22:05:39
回复(0)
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];
}
}
发表于 2019-11-11 16:24:58
回复(0)
public class Solution {
public int minPathSum(int[][] grid) {
if(grid==null||grid[0]==null){
return 0;
}
int row=grid.length;
int col=grid[0].length;
int[][] array=new int[row+1][col+1];
array[0][0]=grid[0][0]; //初始化
for(int i=1;i<row;i++){
array[i][0]=grid[i][0]+array[i-1][0];
}
for(int i=1;i<col;i++){
array[0][i]=grid[0][i]+array[0][i-1];
}
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
array[i][j]=grid[i][j]+Math.min(array[i-1][j],array[i][j-1]);
}}
return array[row-1][col-1];
}
}
public int minPathSum(int[][] grid) {
if(grid==null||grid[0]==null){
return 0;
}
int row=grid.length;
int col=grid[0].length;
int[][] array=new int[row+1][col+1];
array[0][0]=grid[0][0]; //初始化
for(int i=1;i<row;i++){
array[i][0]=grid[i][0]+array[i-1][0];
}
for(int i=1;i<col;i++){
array[0][i]=grid[0][i]+array[0][i-1];
}
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
array[i][j]=grid[i][j]+Math.min(array[i-1][j],array[i][j-1]);
}}
return array[row-1][col-1];
}
}
发表于 2019-07-25 20:22:06
回复(0)
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有点**
发表于 2018-09-06 10:18:49
回复(0)
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];
}
}
发表于 2018-06-30 16:53:48
回复(0)
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];
}
}
编辑于 2017-08-06 13:35:10
回复(5)
/**
动态规划的核心：
找出状态转移方程，初始值，找出边界值，划分出子问题
*/
import java.util.*;
public class Solution {
public int minPathSum(int[][] grid) {
int M = grid.length;
int N = grid[M-1].length;
int[][] result = new int[M][N];
if(M==1&&N==1)
{
return grid[0][0];
}
else
{
//初始化
result[0][0] = grid[0][0];
//对于同一列，从上往下比较
for(int i=1;i<M;i++)
{
result[i][0]= result[i-1][0]+grid[i][0];
}
//对于同一行，左往右比较
for(int j=1;j<N;j++)
{
result[0][j]= result[0][j-1]+grid[0][j];
}
for(int i=1;i<M;i++)
{
for(int j=1;j<N;j++)
{
result[i][j] =
Math.min(result[i-1][j],result[i][j-1])+grid[i][j];
}
}
}
return result[M-1][N-1];
}
}
发表于 2017-07-12 20:44:54
回复(0)
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];
}
}
发表于 2017-06-21 13:05:35
回复(0)
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]; }
发表于 2017-03-12 12:20:31
回复(0)
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];
}
}
发表于 2016-11-05 17:24:52
回复(0)
我是一个 菜鸟 我不会vector 只会c 所以简单用 java写了一下
纪念我的第一道动态规划 我已经大四了还没还没offer 有点累。
public class Solution {
public int min(int a,int b){ return ((a)<(b)?(a):(b));
}
public int minPathSum(int[][] grid) {
int i,j,m,n;
int [][] dp = new int[100][100];
n = grid.length;
m = grid[0].length;
dp[0][0]=grid[0][0];
for(i = 1;i<m;i++){
dp[0][i] = dp[0][i-1]+grid[0][i];//横
}
for(j = 1;j<n;j++){
dp[j][0] = dp[j-1][0]+grid[j][0];//纵
}
for(i=1;i<n;i++)
for(j=1;j<m;j++){ //中间部分的计算
dp[i][j] =
min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
}
return dp[n-1][m-1];
}
}
发表于 2016-10-26 14:45:07
回复(2)
问题信息
难度：
16条回答
66收藏
27220浏览
通过挑战的用户
查看代码-
2022-12-23 15:53:29
-
2022-12-18 14:39:19
-
2022-12-16 22:06:06
-
2022-09-16 15:40:36 -
2022-09-14 17:45:17
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
