64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

1 3 1
1 5 1
4 2 1

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

1 2 3
4 5 6

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

analyze

动态规划一:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const m = grid.length
  const n = grid[0].length
  const cache = {}
  return findMinCount(m - 1, n - 1, grid, cache)
}

function findMinCount(x, y, grid, cache) {
  if (cache[`${x}~${y}`]) {
    return cache[`${x}~${y}`]
  }

  let count = 0

  if (x === 0 && y === 0) {
    count = grid[0][0]
  } else if (x === 0) {
    count = findMinCount(0, y - 1, grid, cache) + grid[0][y]
  } else if (y === 0) {
    count = findMinCount(x - 1, y, grid, cache) + grid[x][0]
  }

  if (x > 0 && y > 0) {
    count = Math.min(findMinCount(x - 1, y, grid, cache), findMinCount(x, y - 1, grid, cache)) + grid[x][y]
  }

  cache[`${x}~${y}`] = count

  return count
}

动态规划二:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const mLength = grid.length
  const nLength = grid[0].length
  const cache = []
  for (let m = mLength - 1; m >= 0; m--) {
    for (let n = nLength - 1; n >= 0; n--) {
      if (!cache[m]) cache[m] = []
      if (m + 1 >= mLength && n + 1 >= nLength) {
        cache[m][n] = grid[m][n]
      } else if (m + 1 >= mLength) {
        cache[m][n] = cache[m][n + 1] + grid[m][n]
      } else if (n + 1 >= nLength) {
        cache[m][n] = cache[m + 1][n] + grid[m][n]
      } else {
        cache[m][n] = Math.min(cache[m + 1][n], cache[m][n + 1]) + grid[m][n]
      }
    }
  }
  return cache[0][0]
}

Similar Title

120