### 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 == gridi.length
• 1 <= m, n <= 200
• 0 <= gridi <= 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]
}``````

120