题解 | 矩阵的最小路径和

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix int整型二维数组 the matrix
 * @return int整型
 */
function minPathSum( matrix ) {
    // write code here
    const m = matrix.length
    const n = matrix[0].length
    const dp = Array.from({length: m+1 }, ()=> Array( n+1 ).fill(0))
    for (let i=0 ; i<m; i++) {
        for (let j=0; j<n; j++) {
            if (i === 0 && j === 0) {
                dp[i][j] = matrix[i][j]
            }
            else if ( i === 0) {
                dp[i][j] = matrix[i][j] + dp[i][j-1]
            }
            else if ( j === 0) {
                dp[i][j] = matrix[i][j] + dp[i-1][j]
            }
            else {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j]
            }
        }
    }
    return dp[m-1][n-1]
}
module.exports = {
    minPathSum : minPathSum
};