矩阵的最小路径和

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

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

输出

备注:

算法知识视频讲解

Javascript

萌萌94

发表于 2022-06-02 18:01:40 回复(0)

Javascript

大智若‘俞’

/**
 * 
 * js实现
 */
function minPathSum( matrix ) {
    // write code here 动态规划，
    let dp = new Array(matrix.length).fill(0).map(item => new Array(matrix[0].length));
    dp[0][0] = matrix[0][0];
    for(let i = 1; i < matrix.length; i++) {
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }
     for(let i = 1; i < matrix[0].length; i++) {
        dp[0][i] = dp[0][i-1] + matrix[0][i];
    }
    for(let i = 1; i < matrix.length; i++) {
        for(let j = 1; j < matrix[0].length; j++) {
            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];
}

发表于 2022-03-28 20:27:38 回复(0)

JavaScript

splwany

function minPathSum( matrix ) {
    if (matrix.length === 0) return 0;
    const [n, m] = [matrix.length, matrix[0].length];
    const dp = Array.from(new Array(n), () => new Array(m).fill(0));
    dp[0][0] = matrix[0][0];
    for (let i = 1; i < m; i++) dp[0][i] = dp[0][i - 1] + matrix[0][i];
    for (let i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + matrix[i][0];
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
        }
    }
    return dp[n - 1][m - 1];
}

发表于 2021-04-02 15:55:01 回复(0)

JavaScript

别卷啦！

var minPathSum = function(matrix) {
let m = matrix.length, n=matrix[0].length
if(!m ||!n) return 0
for(let i = 0;i<m;i++){
    for(let j = 0;j<n;j++){
        if(i==0&&j>0){
            matrix[0][j] += matrix[0][j-1]
        }else if(i>0&&j==0){
            matrix[i][0] +=matrix[i-1][0]
        }else if(i>0&&j>0){
            matrix[i][j] += Math.min(matrix[i-1][j],matrix[i][j-1])
        }
    }
}
return matrix[m-1][n-1]
};

发表于 2021-01-08 16:21:37 回复(0)