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 13111 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