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

//动态规划
/**
 * 
 * @param matrix int整型二维数组 the matrix
 * @return int整型
 */
function minPathSum( matrix ) {
    let x = matrix.length;
    let y = matrix[0].length;
    let dp = Array(x).fill(0).map(x => Array(y).fill(0));
    dp[0][0] = matrix[0][0];
    for (let i = 1; i < y; i++) {
        dp[0][i] = dp[0][i-1] + matrix[0][i];
    }
    for (let i =1 ; i< x; i++) {
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }
    for (let i=1; i< x; i++){
        for(let j=1; j<y; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
        }
    }
    return dp[x-1][y-1];
}



module.exports = {
    minPathSum : minPathSum
};