首页 > 试题广场 >

矩阵的最小路径和

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

热度指数：92920 时间限制：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]]

输出

备注:

算法知识视频讲解

C++

哈哈哈哈哈滴滴

1.超时的简单方法
class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */     int minPath(vector<vector<int>> &matrix, int i, int j){
        int n = matrix.size();
        int m = matrix[0].size();
        //如果就1*1，里面就一个值
        if(i == n-1 && j == m-1){return matrix[i][j];}
        //如果只有一行，只能向右走
        if(i == n-1 && j != m-1) return matrix[i][j]+minPath(matrix, i, j+1);
        //如果只有一列，只能向下走
        else if(i != n-1 && j == m-1) return matrix[i][j]+minPath(matrix, i+1, j);
        //正常情况
        int a = minPath(matrix, i, j+1); // 向右走
        int b = minPath(matrix, i+1, j); // 向下走
        // 看看向哪边走路径比较小
        return a < b ? matrix[i][j] + a : matrix[i][j] + b;
    }
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        return minPath(matrix, 0, 0);
    }
};
2.动态规划
class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        dp[1][1] = matrix[0][0];
        for(int i=2; i<=m; i++) dp[1][i] = dp[1][i-1]+matrix[0][i-1];
        for(int i=2; i<=n; i++) dp[i][1] = dp[i-1][i]+matrix[i-1][0];
        for(int i=2; i<=n; i++){
            for(int j=2; j<=m; j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])+matrix[i-1][j-1];
            }
        }
        return dp[n][m];
    }
};

发表于 2021-08-21 13:59:24 回复(0)

offer保命

使用动态规划的迭代法：因为只能向下和向右走，dp[i][j]表示从左上到当前i行j列格子的最短距离

确定临界值：第一行第一列的值可确定，第一行为 $dp[1][j]=dp[1][j-1]+matrix[0][j-1]$

第一列为：

$dp[i][1]=dp[i-1][1]+matrix[i-1][0]$

状态转移公式：

$dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i-1][j-1]$

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        /*
        ** 使用动态规划的迭代法实现，dp[i][j]
        */
        int n=matrix.size();
        int m=matrix[0].size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        dp[1][1]=matrix[0][0];
        //初始化dp的第一行第一列
        for(int i=2;i<=m;i++)
        {
            dp[1][i]=dp[1][i-1]+matrix[0][i-1];
        }
        for(int i=2;i<=n;i++)
        {
            dp[i][1]=dp[i-1][1]+matrix[i-1][0];
        }
        //状态转移方程dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i-1][j-1]
        for(int i=2;i<=n;i++)
        {
            for(int j=2;j<=m;j++)
            {
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+matrix[i-1][j-1];
            }
        }
        return dp[n][m];
    }
};

发表于 2021-03-19 17:03:47 回复(1)

C/C++

木析

动态规划，简化空间为一维数组

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int row=matrix.size();
        if(row==0) {
            return 0;
        }
        int col=matrix[0].size();
        vector<int> dp(col,0);
        dp[0]=matrix[0][0];
        for(int i=1;i<col;i++) {
            dp[i]=dp[i-1]+matrix[0][i]; //到达第一行每个点的路径和
        }
        
        for(int i=1;i<row;i++) {
            for(int j=0;j<col;j++) {
                int left=INT_MAX; //从左边到达该点
                int up=dp[j]; //从上边到达该点
                if(j>0) {
                    left=dp[j-1];
                }
                dp[j]=min(left,up)+matrix[i][j];
            }
        }
        return dp[col-1];
    }
};

发表于 2021-03-28 16:26:36 回复(0)

Java

肥猿

解题思路：动态规划，状态转移方程为dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j]

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        //dp解法
        int len1=matrix.length;
        int len2=matrix[0].length;
        int[][] dp=new int[len1][len2];
        dp[0][0]=matrix[0][0];
        for(int i=1;i<len1;i++) dp[i][0]=dp[i-1][0]+matrix[i][0];
        for(int i=1;i<len2;i++) dp[0][i]=dp[0][i-1]+matrix[0][i];
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }
        return dp[len1-1][len2-1];
    }
}

发表于 2021-03-15 14:20:42 回复(0)

Python

LHC0512

Python 记忆化搜索，通过

from functools import lru_cache

class Solution:
    def minPathSum(self, matrix):
        n = len(matrix) - 1
        m = len(matrix[0]) - 1
        self.matrix = matrix
        return self.__gen(n, m)

    @lru_cache(maxsize=4000000)
    def __gen(self, i, j):
        if i > 0 and j > 0:
            return self.matrix[i][j] + min(self.__gen(i - 1, j), self.__gen(i, j - 1))
        elif i > 0:
            return self.matrix[i][j] + self.__gen(i - 1, j)
        elif j > 0:
            return self.matrix[i][j] + self.__gen(i, j - 1)
        else:
            return self.matrix[i][j]

发表于 2021-02-23 17:39:10 回复(0)

Python

sk8_wt

class Solution:
    def minPathSum(self , matrix ):
        rows = len(matrix)
        cols = len(matrix[0])
        dp = [[0]*cols for _ in range(rows)]
        for col in range(cols):
            dp[0][col] = sum(matrix[0][:col+1])
        for row in range(rows):
            sum_ = 0
            for i in range(row+1):
                sum_ += matrix[i][0]
            dp[row][0] = sum_
        for row in range(1,rows):
            for col in range(1,cols):
                dp[row][col] = min(dp[row-1][col],dp[row][col-1])+matrix[row][col]
        return dp[-1][-1]

用python写动态规划，超时，通过62.5%

发表于 2020-08-30 15:51:35 回复(2)

Python

擎天柱领袖

class Solution:
def minPathSum(self , matrix ):
# DP
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i == j == 0: continue
elif i == 0: matrix[i][j] = matrix[i][j - 1] + matrix[i][j]
elif j == 0: matrix[i][j] = matrix[i - 1][j] + matrix[i][j]
else: matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1]) + matrix[i][j]
return matrix[-1][-1]

case通过率为62.50% 有人能更快的吗

发表于 2020-08-15 20:25:32 回复(3)

henry_shine

python无法通过，超过4s时间，，通过62.5%的case

编辑于 2020-08-25 11:27:33 回复(3)

cqu后起之秀

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = 0;
        vector<vector<int> >dp(n, vector<int>(m));
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = min(dp[i - 1][j] + matrix[i][j], dp[i][j - 1] + matrix[i][j]);
                ans = dp[i][j];
            }
        }
        return ans;
    }
};

发表于 2020-11-07 14:23:17 回复(0)

给我offer我要offer

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];
        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][j-1],dp[i-1][j])+matrix[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

发表于 2020-08-28 19:20:34 回复(1)

Python3

蓝猫小哥哥

#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix ):
        # write code here
        '''
        确实是很基础的二维动态规划。
        思路与递归正好相反：自顶向下的生成路径和，自底向上的查找最小路径和。
        dp[i][j]:从左上点(0,0)到点(i,j)的最小路径和。
        初始化：dp数组维度为m*n，初始化每个元素为0。第0行和第0列的最小路径和就是其行列和。先行加和初始化第0行和第0列。
        当然也可以不做此操作，初始化dp数组维度为m+1，n+1，且第0行第0列的第二个元素初始化为0（保证dp[1][1]=mat[0][0]），其他初始化为正无穷即可。
        递推公式：dp[i][j] = min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
        时间复杂度：O(mn),空间复杂度：O(mn)/O(n)。
        可以进行空间压缩，由于我们的计算只涉及左边元素和上面元素，所以只需要一个2*n的空间即可（滚动数组）
        '''
        m , n = len(matrix),len(matrix[0])
        dp = [[100000000]*(n+1) for _ in range(2)]
        dp[0][1],dp[1][1] = 0,0
        for i in range(1,m+1):
            
            for j in range(1,n+1):
                dp[i%2][j] = min(dp[(i-1)%2][j],dp[i%2][j-1])+matrix[i-1][j-1]
        return dp[i%2][n]
        
#         m , n = len(matrix),len(matrix[0])
#         dp = [[100000000]*n for _ in range(m)]
#         dp[0][0] = matrix[0][0]
#         for i in range(1,m):
#             dp[i][0] = dp[i-1][0]+matrix[i][0]
#         for i in range(1,n):
#             dp[0][i] = dp[0][i-1]+matrix[0][i]
#         for i in range(1,m):
#             for j in range(1,n):
#                 dp[i][j] = min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
#         #print(dp)
#         return dp[m-1][n-1]
        
#         '''
#         递归思路：每次选择向右或向下的最短路径。
#         时间复杂度：我没算错的话是O(2^mn)，空间复杂度由于调用系统栈其实也是这么多，铁定超时。
#         （因为递归是遍历所有的路径，自顶向下的查询。）
#         '''
#         self.m,self.n = len(matrix)-1,len(matrix[0])-1
#         def minpsum(i,j):
#             if i == self.m and j == self.n:
#                 return matrix[i][j]
#             if i == self.m:
#                 return matrix[i][j]+minpsum(i, j+1)
#             if j == self.n:
#                 return matrix[i][j]+minpsum(i+1, j)
#             right = minpsum(i, j+1)
#             down = minpsum(i+1, j)
#             return matrix[i][j]+min(right,down)
#         return minpsum(0, 0)

编辑于 2021-07-22 11:32:47 回复(0)

Python 3

霸气青提

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        for i in range(1, len(matrix)):
            matrix[i][0] += matrix[i-1][0]
        for j in range(1, len(matrix[0])):
            matrix[0][j] += matrix[0][j-1]
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1])
        return matrix[-1][-1]

发表于 2022-07-26 10:31:56 回复(0)

Java

***

public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    HashMap<String,Integer> map=new HashMap<String,Integer>();
    public int minPathSum (int[][] matrix) {
        // write code here
         if(matrix==null){
            return 0;
        }
        return dfs(matrix,matrix.length-1,matrix[0].length-1); 
    }
    
    public int  dfs(int[][] matrix,int m,int n){
       if(m==0&&n==0)
            return matrix[m][n];
        String key=m+"-"+n;
        if(map.containsKey(key)){
            return map.get(key);
        }
        int res=0;
        if(m==0){
             res= matrix[m][n]+dfs(matrix,m,n-1);
        }else if(n==0){
              res= matrix[m][n]+dfs(matrix,m-1,n); 
        }else{
            res= matrix[m][n]+Math.min(dfs(matrix,m-1,n),dfs(matrix,m,n-1));
        }
        map.put(key,res);
        return res;  
    }
}

发表于 2022-03-10 14:38:26 回复(0)

Java

牛气嘣嘣

采用递归：遍历二维数组每一个元素，一共有四种情况

当前节点是起点，直接跳过此次循环
当前节点在第一行，则上一个节点只能是左边节点，matrix[i][j] = matrix[i][j-1] + matrix[i][j]
当前节点在第一列，则上一个节点只能是上边节点，matrix[i][j] = matrix[i-1][j] + matrix[i][j]
否则，上一个节点就可能来自左边节点或上边节点，matrix[i][j] = Math.min(matrix[i-1][j], matrix[i][j-1]) + matrix[i][j]
最后返回：matrix[matrix.length-1][matrix[0].length-1]

发表于 2021-09-09 23:04:39 回复(0)

又笨又懒不想上课

记忆化递归

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int res = findpath(matrix, matrix.length - 1, matrix[0].length - 1, new HashMap<String,Integer>());
        return res;
    }
    private int findpath(int[][] mat, int i, int j, Map<String, Integer> map) {
        if(i == 0 && j == 0) {
            return mat[0][0];
        }
        int res = 0;
        String key = i +"a" + j;
        if(map.containsKey(key)) return map.get(key);
        if(i == 0) {
            res = mat[i][j] + findpath(mat, i, j - 1, map);
        } else if(j == 0) {
            res = mat[i][j] + findpath(mat, i - 1, j, map);
        } else {
            res = mat[i][j] + Math.min(findpath(mat, i - 1, j, map), findpath(mat, i, j - 1, map));
        }
        map.put(key,res);
        return res;
        
    }
}

发表于 2021-06-03 11:35:37 回复(0)

一个优雅的程序猿

#define min(a,b)    (a<b?a:b)
int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
    int dp[2000][2000],i,j;
    dp[0][0] = matrix[0][0];
    for(i=1; i<matrixRowLen; i++) 
        dp[i][0] = matrix[i][0]+dp[i-1][0];
    for(i=1; i<*matrixColLen; i++) 
        dp[0][i] = matrix[0][i]+dp[0][i-1];
    
    for(i=1; i<matrixRowLen; i++) 
        for(j=1; j<*matrixColLen; j++) 
            dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1]);
    return dp[matrixRowLen-1][*matrixColLen-1];
}

编辑于 2024-03-24 16:53:00 回复(0)

实实实实

#include <vector>

class Solution {

public:

/**

* @param matrix int整型vector<vector<>> the matrix

* @return int整型

int minPathSum(vector<vector<int> >& matrix) {

// write code here

int m = matrix.size(), n = matrix[0].size();

vector<vector<int> > dp(m, vector<int>(n, 0));

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

for (int i = 1; i < m; i++) {

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

}

for (int i = 1; i < n; i++) {

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

}

for (int i = 1; i < m; i++) {

for (int j = 1; j < n; j++) {

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

}

return dp[m-1][n-1];

}

};

发表于 2023-04-03 13:42:34 回复(0)

牛客792028132号

#define  MIN(a,b)   ((a) > (b) ? (b) : (a))

int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
    int i=0,j=0;
    int min = 0;
    int **array = (int**)malloc( (matrixRowLen)*sizeof(int*));

    for(i=0;i<=matrixRowLen;i++){           //创建二维数组
        array[i] = calloc(1,sizeof(int)* (*matrixColLen));
    }

    array[0][0] = matrix[0][0];
    for(i=1;i<*matrixColLen;i++){           //计算第0行
        array[0][i] = matrix[0][i] + array[0][i-1];
    }

    for(i=1;i<matrixRowLen;i++){            //计算第0列
        array[i][0] = matrix[i][0] + array[i-1][0];
        //printf("a[%d][%d] = %d\r\n",i,0,array[i][0]);
    }

    for(i=1;i<matrixRowLen;i++){            //计算剩余行列
        for(j=1;j< *matrixColLen;j++){
            array[i][j] = MIN(array[i-1][j], array[i][j-1]) + matrix[i][j];   //状态转移公式
        }
    }

    min = array[matrixRowLen-1][*matrixColLen-1];   //暂存最小路径值

    for(i=0;i<matrixRowLen;i++){    //释放资源
        free(array[i]); 
    }
    free(array);

    return min;
}

发表于 2023-01-17 14:44:51 回复(0)

C++

Spectre_

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // 时间复杂度O(NM)，空间复杂度O(NM)
        int n = matrix.size(), m = matrix[0].size();
        int dp[n][m];
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < n; ++i) dp[i][0] = matrix[i][0] + dp[i - 1][0];
        for (int j = 1; j < m; ++j) dp[0][j] = matrix[0][j] + dp[0][j - 1];
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][m - 1];
    }
};

发表于 2022-11-07 17:36:44 回复(0)

聪敏的大白菜向光而行

/**
*
* @param matrix int整型二维数组 the matrix
* @param matrixRowLen int matrix数组行数
* @param matrixColLen int* matrix数组列数
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int min(int a,int b){
if(a<b)return a;
else
return b;
}
int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
// write code here
int m=matrixRowLen;
int n=*matrixColLen;
int dp[m][n];
dp[0][0]=matrix[0][0];
for(int i=1; i<m; i++){
dp[i][0]=dp[i-1][0]+matrix[i][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++){
for(int j=1; j<n; j++){
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
}
}
return dp[m-1][n-1];
}

发表于 2022-07-25 17:22:51 回复(0)