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

很简单的dp，

状态转移方程：$dp[i][j]=matrix[i][j]+Math\mathrm{.}min(dp[i-1][j],dp[i][j-1])dp[i][j]\; =\; matrix[i][j]\; +\; Math.min(dp[i-1][j],dp[i][j-1])$

注意dp的第一行和第一列提前算出

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