首页 > 试题广场 >

矩阵的最小路径和

[编程题]矩阵的最小路径和

热度指数：96669 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: $1 \le n,m\le 500$ ，矩阵中任意值都满足 $0 \le a_{i,j} \le 100$

要求：时间复杂度 $O(nm)$

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，

所选择的最小累加和路径如下图所示：

示例1

输入

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

输出

示例2

输入

[[1,2,3],[1,2,3]]

输出

备注:

算法知识视频讲解

Java

fukkk

优雅的写法：

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];
    }

发表于 2025-03-10 18:17:16 回复(0)

Java

人间水长东

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];
    }
}

发表于 2024-09-23 21:47:48 回复(0)

Java

牛客839384289号

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];
}

发表于 2024-05-26 15:53:14 回复(0)

Java

chenyd

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param matrix int整型二维数组 the matrix

* @return int整型

public int minPathSum (int[][] matrix) {

// write code here

//dp[m][n]表示走到m,n的最小加和

//转移方程为f[m,n]=min{f[m-1,n],f[m,n-1]}+matrix[m][n]

int [][]dp = new int[matrix.length][matrix[0].length];

dp[0][0] = matrix[0][0];

for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix[0].length; j++) {

if (i - 1 < 0 && j - 1 < 0) {

dp[i][j] = matrix[i][j];

} else if (i - 1 < 0) {

dp[i][j] = dp[i][j - 1] + matrix[i][j];

} else if (j - 1 < 0) {

dp[i][j] = dp[i - 1][j] + matrix[i][j];

} else {

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];

}

return dp[matrix.length - 1][matrix[0].length - 1];

}

发表于 2023-07-19 18:15:59 回复(0)

Java

做则必成的勇气和信心

 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];
    }

发表于 2023-07-11 16:29:47 回复(0)

Java

Zhima1234

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];
    }
}

发表于 2023-05-31 10:07:38 回复(0)

Java

键盘都敲坏了.

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];
    }
}

发表于 2022-11-22 14:46:07 回复(0)

Java

624huiguorou

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];
    }

    
}

发表于 2022-09-19 16:35:26 回复(0)

Java

超可爱超超

        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];

发表于 2022-09-06 10:48:34 回复(0)

Java

程序员大鹏

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];
    }

发表于 2022-08-25 00:08:45 回复(0)

Java

yxjing

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];
    }
}

发表于 2022-08-08 15:37:22 回复(0)

Java

牛客5514606号

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];
    }
}

发表于 2022-07-16 17:38:40 回复(0)

Java

进入人才池

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];
    }
}

发表于 2022-06-19 22:06:07 回复(0)

Java

NiKoDad

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];
    }
}

发表于 2022-06-02 15:14:21 回复(0)

Java

毛豆来啦

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];
    }
}

发表于 2022-05-10 14:53:00 回复(0)

Java

精灵鼠201906031611131

和大家的思路是一样的。达到x,y可能是从x-1,y 或者是x,y-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];
    }
}

发表于 2022-04-21 16:09:56 回复(0)

Java

輝长六加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];
  }
}

发表于 2022-04-04 11:20:02 回复(0)

Java

江_小_白

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];
    }
}

发表于 2022-03-25 20:35:48 回复(0)