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

动态规划

• 设置一个二维表$dp[i][j]dp[i][j]$表示从$(0,0)(0,0)$到达$(i,j)(i,j)$的最短路径
• 状态转移方程为 $dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]dp[i][j]\; =\; min(dp[i-1][j],\; dp[i][j-1])\; +\; matrix[i][j]$
• 初始化$dpdp$的第一行和第一列，然后可以利用状态转移方程进行更新，返回$dp[m-1][n-1]dp[m-1][n-1]$

const [m, n] = readline().split(' ').map(x => ~~x)
const matrix = new Array(m).fill(null)
for(let i = 0 ; i < m ; i++) {
    let row = readline().split(' ').map(x => ~~x)
    matrix[i] = row
}

function main(matrix, m, n) {
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
    dp[0][0] = matrix[0][0]
    // 初始化第一行和第一列
    for(let i = 1 ; i < m ; i++) {
        dp[i][0] = dp[i-1][0] + matrix[i][0]
    }
    for(let i = 1 ; i < n ; i++) {
        dp[0][i] = dp[0][i-1] + matrix[0][i]
    }
    // 进行更新
    for(let i = 1 ; i < m ; i++) {
        for(let k = 1 ; k < n ; k++) {
            dp[i][k] = Math.min(dp[i-1][k], dp[i][k-1]) + matrix[i][k]
        }
    }
    return dp[m-1][n-1]
}

console.log(main(matrix, m, n))