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

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""