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;
}
}