# 64. Minimum Path Sum (Medium)

https://leetcode.com/problems/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:

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

## Solutions

``````class Solution {

// This problem is too easy to solve. Apply map to keep track of the minimum path sum for each cell.

Map<String, Integer> visitMap = new HashMap<>();

public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}

return recurse(grid, 0, 0);
}

public int recurse(int[][] grid, int x, int y) {
int rLen = grid.length;
int cLen = grid[0].length;

if (x == rLen - 1 && y == cLen - 1) {
return grid[x][y];
}

if (x >= rLen || x < 0 || y >= cLen || y < 0) {
return -1;
}

String key = x + "#" + y;
if (visitMap.containsKey(key)) {
return visitMap.get(key);
}

int min = Integer.MAX_VALUE;

int[] R = new int[]{0, 1};
int[] C = new int[]{1, 0};

for (int i = 0; i < 2; i++) {
int nx = x + R[i];
int ny = y + C[i];

int rst = recurse(grid, nx, ny);

// unreachable
if (rst < 0) {
continue;
}

min = Math.min(min, rst);
}

int ans = min + grid[x][y];

visitMap.put(key, ans);

return ans;
}
}
``````