64.最小路径和

链接：64.最小路径和
难度：Medium
标签：数组、动态规划、矩阵
简介：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

题解 1 - typescript

• 编辑时间：2020-07-23
• 执行用时：116ms
• 内存消耗：40.5MB
• 编程语言：typescript
• 解法介绍：动态规划,dp[i][j]=i，j 坐标时的最小值。

function minPathSum(grid: number[][]): number {
  const row = grid.length;
  const col = grid[0].length;
  const dp = new Array(row).fill(0).map(_ => new Array(col));
  dp[row - 1][col - 1] = grid[row - 1][col - 1];
  for (let i = row - 1; i >= 0; i--) {
    for (let j = col - 1; j >= 0; j--) {
      const num = grid[i][j];
      if (i === row - 1 && j === col - 1) {
      } else if (i === row - 1) {
        dp[i][j] = dp[i][j + 1] + num;
      } else if (j === col - 1) {
        dp[i][j] = dp[i + 1][j] + num;
      } else {
        dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j]) + num;
      }
    }
  }
  return dp[0][0];
}