### 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 11 5 14 2 1
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]Output: 7Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

1 2 34 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]}

120