首页 > 试题广场 >

矩阵的最小路径和

[编程题]矩阵的最小路径和
  • 热度指数:84674 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个 n * m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。

数据范围: ,矩阵中任意值都满足
要求:时间复杂度

例如:当输入[[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]]

输出

12
示例2

输入

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

输出

7

备注:
1 \leq a_{i,j} \leq 100
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)
使用动态规划的迭代法:因为只能向下和向右走,dp[i][j]表示从左上到当前i行j列格子的最短距离
确定临界值:第一行第一列的值可确定,第一行为
第一列为:

状态转移公式:

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)
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)
动态规划,简化空间为一维数组
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)
解题思路:动态规划,状态转移方程为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 记忆化搜索, 通过
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)
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)
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)
python无法通过,超过4s时间,,通过62.5%的case
编辑于 2020-08-25 11:27:33 回复(3)
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)
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)
#
# 
# @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)
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)
采用递归:遍历二维数组每一个元素,一共有四种情况
  1. 当前节点是起点,直接跳过此次循环
  2. 当前节点在第一行,则上一个节点只能是左边节点,matrix[i][j] = matrix[i][j-1] + matrix[i][j]
  3. 当前节点在第一列,则上一个节点只能是上边节点,matrix[i][j] = matrix[i-1][j] + matrix[i][j]
  4. 否则,上一个节点就可能来自左边节点或上边节点,matrix[i][j] = Math.min(matrix[i-1][j], matrix[i][j-1]) + matrix[i][j]
  5. 最后返回: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)

#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)
#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)
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)
function minPathSum( matrix ) {
    // write code here
    let M = matrix.length, N = matrix[0].length;
    for (let i = 1; i < M; i++) {
        matrix[i][0] += matrix[i-1][0];
    }
    for (let j = 1; j < N; j++) {
        matrix[0][j] += matrix[0][j-1];
    }
    
    for (let i = 1; i < M; i++) {
        for (let 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-06-02 18:01:40 回复(0)