题解 | #矩阵的最小路径和#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix int整型二维数组 the matrix
 * @return int整型
 */
function minPathSum(matrix) {
    // write code here
    // 动态规划，到达某一个点的计算公式如下：
    // dp[i][j] = matrix[i][j]+Math.min(dp[i-1][j],dp[i][j-1])

    if (matrix.length == 0 || matrix[0].length == 0) {return -1;}
    let dp = [];
    for (let i = 0; i < matrix.length; i++) {
        dp.push([])
        for (let j = 0; j < matrix[0].length; j++) {
            if(i==0 && j==0){
                dp[i].push(matrix[i][j])
            }else if(i==0){
                dp[i].push(matrix[i][j]+dp[i][j-1])
            }else if(j==0){
                dp[i].push(matrix[i][j]+dp[i-1][j])
            }else{
                dp[i].push(matrix[i][j]+Math.min(dp[i-1][j],dp[i][j-1]))
            }
        }
    }
    console.log(dp)
    return dp[matrix.length-1][matrix[0].length-1]
}
module.exports = {
    minPathSum: minPathSum,
};