首页 > 试题广场 >

带权值的最小路径和

[编程题]带权值的最小路径和
  • 热度指数：20439 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。
注意：你每次只能向下或向右移动。


示例1

输入

[[1,2],[5,6],[1,1]]

输出

8
算法知识视频讲解
添加回答
Java
lxhao头像 lxhao 
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)
LinuX18头像 LinuX18 
class Solution {
public:
    // 空间复杂度哦（m*n)
    int minPathSum(vector<vector<int> > &grid) 
    {
       int m=grid.size(),n=grid[0].size();
       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];
              if(i!=0 && j==0) grid[i][j] += grid[i-1][j];
              if(i*j!=0)
                  grid[i][j] += min(grid[i-1][j],grid[i][j-1]);
           }
        }
       return grid[m-1][n-1];
    }
};

发表于 2017-07-08 21:26:06 回复(2)
M00N头像 M00N 
package dp;
/**
minimum-path-sum
题目描述
Given a m x n grid filled with non-negative numbers, 
find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
 */
public class Minimumpathsum {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        //第一行
        for (int i = 1; i < n; i++) {
        	dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        //第一列
        for (int i = 1; i < m; i++) {
        	dp[i][0] = dp[i-1][0] + grid[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]) + grid[i][j];
        	}
        }
        
        return dp[m-1][n-1];
    }
}

发表于 2017-04-02 23:36:10 回复(1)
C/C++
Ga_li_dun_farming_guy头像 Ga_li_dun_farming_guy
//方法1，暴力用深搜，超时。换方法。。。。
class Solution {
public:
    set<int> ans;
    void DFS(vector<vector<int> > &grid,int sum, int i , int j)
    {
        if(i >= grid.size() || j >= grid[0].size()) return;
        sum = sum + grid[i][j];
        if(i == grid.size()-1 && j == grid[0].size()-1)
        {
            ans.insert(sum);
            return ;
        }
        DFS(grid,sum,i+1,j);
        DFS(grid,sum,i,j+1);
    }
    int minPathSum(vector<vector<int> > &grid) {
        if(grid.size()== 0) return 0;
        DFS(grid,0,0,0);
        return *ans.begin();
    }
};
//方法二，DP参考各位大佬。
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int h = grid.size();
        if(h == 0) return 0;
        int w = grid[0].size();
        for(int i = 1 ; i != h ; i++)
            grid[i][0] += grid[i-1][0];
        for(int j = 0 ; j != w; j++)
            grid[0][j] += grid[0][j-1];
        for(int i = 1; i < h ; i++)
            for(int j = 1; j < w ; j++)
            {
                grid[i][j] += min(grid[i-1][j] , grid[i][j-1]);
            }
        return grid[h-1][w-1];
    }
};

发表于 2017-11-22 12:20:53 回复(0)
C/C++
卷积神经网络哦头像 卷积神经网络哦

就在原数组上dp 连新数组都不用开

int minPathSum(vector<vector<int> > &grid) {
        int row = grid.size(), col = grid[0].size();
        for(int i = 1; i < row; i++) grid[i][0] += grid[i-1][0];
        for(int i = 1; i < col; i++) grid[0][i] += grid[0][i-1];
        for(int i = 1; i < row; i++)
            for(int j = 1; j < col; j++)
                grid[i][j] += min(grid[i][j-1], grid[i-1][j]);
        return grid[row-1][col-1];
    }
发表于 2019-06-30 19:39:44 回复(0)
C/C++
WZ_Dale头像 WZ_Dale
动态规划
状态：
子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的最短路径
F(i,j): 从(0,0)到达F(i,j)的最短路径
状态递推：
F(i,j) = min{F(i-1,j) , F(i,j-1)} + (i,j)
初始化：
F(0,0) = (0,0)
特殊情况：第0行和第0列
F(0,i) = F(0,i-1) + (0,i)
F(i,0) = F(i-1,0) + (i,0)
返回结果：
F(m-1,n-1) 
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        if(grid.empty()){
            return 0;
        }
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> F(grid);
        for(int i = 1; i < m; ++i){
            F[i][0] = F[i - 1][0] +F[i][0];
        }
        for(int j = 1; j < n; ++j){
            F[0][j] = F[0][j - 1] +F[0][j];
        }
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                F[i][j] = min(F[i - 1][j], F[i][j - 1]) + F[i][j];
            }
        }
        return F[m - 1][n - 1];
    }
};


编辑于 2020-05-11 11:32:40 回复(0)
Java
我要offerrr头像 我要offerrr 
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)
NULL6666头像 NULL6666 
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int row=grid.size();
        int col=grid[0].size();
        for(int i=1;i<row;i++)
            grid[i][0]+=grid[i-1][0];//第一列加上方
        for(int j=1;j<col;j++)
            grid[0][j]+=grid[0][j-1];//第一行加左侧
        for(int i=1;i<row;i++)
            for(int j=1;j<col;j++)
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);//加上方和左侧中的较小值
        return grid[row-1][col-1];
    }
};

发表于 2018-11-04 22:49:19 回复(0)
C/C++
F-L头像 F-L 
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int m = grid.size();
        int n = grid[0].size();
        for(int i = 0; i < m; ++i){
            if(i-1 >= 0)
                grid[i][0] += grid[i-1][0];
            for(int j = 1; j < n; ++j){
                if(i-1 >= 0)
                    grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
                else grid[i][j] += grid[i][j-1];
            }
            
        }
        
        return grid[m-1][n-1];
    }
};

发表于 2018-03-31 17:13:09 回复(0)
Bapee头像 Bapee
二维DP一行写完，不需要额外空间但破坏了原数组 
public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        for(int i = 0 ; i < grid.length ; i++){
            for(int j = 0 ; j <grid[0].length ; j++){
                grid[i][j] += i==0?(j==0?0:grid[i][j-1]):(j==0?grid[i-1][j]:Math.min(grid[i-1][j],grid[i][j-1]));
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

发表于 2018-03-26 20:53:14 回复(0)
大灰兔头像 大灰兔
简单的二维DP 
class Solution(object):
    def minPathSum(self, grid):
        n = len(grid)
        m = len(grid[0])
        dp = [[0] * m for i in range(n)]
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0 and j != 0:
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                elif i != 0 and j == 0:
                    dp[i][j] = dp[i - 1][j] + grid[i][j]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[-1][-1]

发表于 2017-10-09 13:50:08 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
  		int m = grid.size();
		int n = grid[0].size();
		
		int dp[m][n];
		dp[0][0] = grid[0][0];
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(i==0 && j!=0)
					dp[i][j] = dp[i][j-1] + grid[i][j];
				else if(j==0 && i!=0)
					dp[i][j] = dp[i-1][j] + grid[i][j];
				else if(i*j != 0)
					dp[i][j] = min(dp[i-1][j]+grid[i][j] , dp[i][j-1]+grid[i][j]);
			}
		}
		return dp[m-1][n-1];
    }
};

发表于 2017-08-07 00:55:16 回复(0)
Java
詆調壹點头像 詆調壹點 
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)
Alex-大伟头像 Alex-大伟 
package alex.suda.leetcode;

public class MinPathSum {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

	public static int minPathSum(int[][] grid) {
		int m = grid.length;
		int n = grid[0].length;
		int[][] dp = new int[m][n];//dp[i][j]表示达到(i,j)位置时,最小的路径和
		//初始化
		dp[0][0] = grid[0][0];
		for(int i=1;i<m;i++){
			dp[i][0] = dp[i-1][0] + grid[i][0];
		}
		for(int j=1;j<n;j++){
			dp[0][j] = dp[0][j-1] + grid[0][j];
		}
		for(int i=1;i<m;i++){
			for(int j=1;j<n;j++){
				dp[i][j] = Math.min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j]);
			}
		}
		return dp[m-1][n-1];
	}
}


发表于 2016-10-26 16:08:55 回复(0)
Java
Caffeine头像 Caffeine
我是一个 菜鸟 我不会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)
...王嘉廉睿头像 ...王嘉廉睿 
public class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length;//行数
        int n=grid[0].length;//列数
        int temp=0;
        if(m==1){//当只有一行的情况
            for(int i=0;i<n;i++){
                temp+=grid[0][i];
            }                
            return temp;
        }
        if(n==1){//当只有一列的情况
            for(int i=0;i<m;i++){
                temp+=grid[i][0];
            }                
            return temp;
        }
        //二维数组动态规划仅需要一维空间大小
        int[] sum = new int[n];//sum[i]代表当前节点的上方节点总路径值
        sum[0]=grid[0][0];
        for(int i=1;i<n;i++){//先计算第一行的路径值
        	sum[i]=sum[i-1]+grid[0][i]; 	   
        }            
        temp=0;//代表当前节点的左节点总路径值
        for(int i=1;i<m;i++){
            temp=grid[i][0]+sum[0];
            sum[0]=temp;
            for(int j=1;j<n;j++){
                sum[j]=grid[i][j]+min(temp,sum[j]);
                temp=sum[j];
            }
        }
        return temp;
    }
    int min(int x,int y){
        return x<y?x:y;
    }
}

编辑于 2016-10-18 20:50:10 回复(1)
淡泊宁静吴传奇头像 淡泊宁静吴传奇 
class Solution 
{
public:
    int minPathSum(vector<vector<int> > &grid) 
    {
        int a=grid.size(),b=grid[0].size();
        for(int i=1;i<a;++i)grid[i][0]=grid[i][0]+grid[i-1][0];
        for(int i=1;i<b;++i)grid[0][i]=grid[0][i]+grid[0][i-1];
        for(int i=1;i<a;++i)
            for(int j=1;j<b;++j)
            grid[i][j]=grid[i][j]+min(grid[i-1][j],grid[i][j-1]);
        return grid[a-1][b-1];
    }
};

发表于 2016-09-04 22:29:38 回复(0)
老石基头像 老石基 
public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid==null||grid.length==0)
    		return 0;
    	for(int j = 1;j<grid[0].length;j++)
    		grid[0][j] += grid[0][j-1];
    	if(grid.length==1)
    		return grid[0][grid[0].length-1];
    	
    	for(int i = 1;i<grid.length;i++){
    		for(int j = 0;j<grid[i].length;j++){
    			int cost = j==0?grid[i-1][j]:Math.min(grid[i-1][j], grid[i][j-1]);
    			grid[i][j] += cost;
    		}
    	}
    	return grid[grid.length-1][grid[0].length-1];
    }
}

发表于 2016-06-03 10:32:28 回复(0)
C/C++
Flynn_Thiago头像 Flynn_Thiago
动态规划，一维数组遍历   
 int minPathSum(vector<vector<int> > &grid) {
        int m = grid.size();
        int n = grid[0].size();
        if(m==0 || n==0)
            return 0;
        vector<int> dp(n,0);
        dp[0] = grid[0][0];
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0)
                {
                    if(j!=0)
                        dp[j] = dp[j-1] + grid[i][j];
                    else
                        dp[j] = grid[i][j];
                }else
                {
                    if(j!=0)
                        dp[j] = min(dp[j],dp[j-1]) + grid[i][j];
                    else
                        dp[j] += grid[i][j];
                }
            }
        }
        return dp[n-1];
    }
发表于 2017-09-07 16:24:49 回复(0)
王大爷头像 王大爷 
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0]=grid[0][0];
        for(int j=1;j<n;++j)
            dp[0][j]=dp[0][j-1]+grid[0][j];
        for(int i=1;i<m;++i)
            dp[i][0]=dp[i-1][0]+grid[i][0];
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

发表于 2017-09-06 15:00:27 回复(0)
提交观点

问题信息

动态规划 数组
难度：
114条回答 27574浏览

热门推荐

通过挑战的用户

查看代码

相关试题

带权值的最小路径和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号