矩阵的最小路径和

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

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

输出

备注:

算法知识视频讲解

一个优雅的程序猿

#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)

leiyu511

题目里面要求了0<=ai,j<=100,但测试用例里面超过了100

发表于 2023-02-08 16:14:22 回复(0)

算帝

int min(int a, int b)
{
    return a < b ? a : b;
}

int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
    int m = matrixRowLen;
    int n = *matrixColLen;
    int (*dp)[n] = (int (*)[n])calloc(m*n, sizeof(int)); //dp[i][j]的值为从(0,0)到(i,j)的最小路径和
    dp[0][0] = matrix[0][0];   //dp数组初始化，第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];
}

发表于 2023-01-08 19:53:42 回复(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)

海饼干666

/**
*
* @param matrix int整型二维数组 the matrix
* @param matrixRowLen int matrix数组行数
* @param matrixColLen int* matrix数组列数
* @return int整型
*/
int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
    // write code here
    if(matrixRowLen == 0 || *matrixColLen == 0) return 0;
    int row = matrixRowLen, col = *matrixColLen;

    int **way = (int **)malloc(row*sizeof(int*));
        for(int i =0; i < row; i++)
        {
            way[i] = (int*)malloc(col*sizeof(int));
            memset(way[i], 0, col);
        }

        way[0][0] = matrix[0][0];
        for(int i = 1; i < row; i++) way[i][0] = way[i-1][0] + matrix[i][0];
        for(int j = 1; j < col; j++) way[0][j] = way[0][j-1] + matrix[0][j];
        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < col; j++)
            {
                if(way[i-1][j] <= way[i][j-1]) way[i][j] = way[i-1][j] + matrix[i][j];
                else way[i][j] = way[i][j-1] + matrix[i][j];
            }
        }

        return way[row-1][col-1];
}

发表于 2021-08-28 09:15:17 回复(0)