https://leetcode-cn.com/problems/minimum-path-sum/ 数组、动态规划

动态规划

image.png

  1. function minPathSum(grid: number[][]): number {
  2.     const m = grid[0].length
  3.     const n = grid.length
  5.     for(let x = 1; x < m; x++) {
  6.         grid[0][x] = grid[0][x] + grid[0][x - 1]
  7.     }
  9.     for(let y = 1; y < n; y++) {
  10.         grid[y][0] = grid[y][0] + grid[y - 1][0]
  11.     }
  13.     for(let y = 1; y < n; y++) {
  14.         for(let x = 1; x < m; x++) {
  15.             grid[y][x] = Math.min(grid[y -1][x], grid[y][x - 1]) + grid[y][x]
  16.         }
  17.     }
  19.     return grid[n - 1][m - 1]
  20. };