(Minimum Path Sum)

Given a m \times 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.

Thoughts:
Because the grid is filled with non-negative numbers. Standing at any position (i, j), the minimum sum we can get is \text{grid}[i,j] + \min(minimum sum starting from[i+1,j], minimum sum starting from [i,j+1]). Hence we find the recursive structure of this problem. The base case would be one element only, one row only and one column only. Notice that we could end up with repeating computations a lot (e.g., right->down and down->right), hence we should employ dynamic programming, in which we introduce a hashmap to cache the partial result.

Code (Java):

public class Solution {
    
    private Map<List<Integer>, Integer> map = 
            new HashMap<List<Integer>, Integer>();
    
    public int minPathSum(int[][] grid) {
        map.clear();
        return minPathSumRec(grid, 0, 0);
    }
    
    private int minPathSumRec(int[][] grid, int i, int j) {
        List<Integer> pair = new ArrayList<Integer>();
        pair.add(i);
        pair.add(j);
        if(map.get(pair) != null)
           return map.get(pair);
        else {
            int r = grid[i][j];;
            if(i == grid.length-1 && j == grid[0].length - 1)
                r += 0; 
            else if(i == grid.length - 1)
                r += minPathSumRec(grid, i, j + 1);
            else if(j == grid[0].length - 1)
                r += minPathSumRec(grid, i + 1, j);
            else
                r += Math.min(minPathSumRec(grid, i + 1, j), 
                        minPathSumRec(grid, i, j + 1));
            map.put(pair, r);
            return r;
        }
    }
}

Code (C++):

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        cache.clear();
        return minPathSumRec(grid, 0, 0);
    }
    
private:
    map<vector<int>, int> cache;

    int minPathSumRec(vector<vector<int> > &grid, int i, int j) {
        vector<int> pair(2);
        pair[0] = i;
        pair[1] = j;
        if(cache.find(pair) != cache.end())
            return cache[pair];
        else {
            int r = grid[i][j];
            if(i == grid.size() -1 && j == grid[0].size() - 1)
                r += 0;
            else if(i == grid.size() - 1)
                r += minPathSumRec(grid, i, j + 1);
            else if(j == grid[0].size() - 1)
                r += minPathSumRec(grid, i + 1, j);
            else
                r += min(minPathSumRec(grid, i, j + 1), 
                        minPathSumRec(grid, i + 1, j));
            cache[pair] = r;
            return r;
        }
    }
};
Advertisements

1 Comment (+add yours?)

  1. Nikhil Menon
    Jun 19, 2014 @ 17:27:24

    Hi Runhe,

    Nice work with the blog.

    If I could suggest an optimization, you could use an array of integers instead of the the has map of list of integers to integer. All we need to do is convert the indexes of the grid as if they belonged to a linear data structure.

    In this case, it would be:

    Total column count *i + j,

    Where i => row index of cell
    j => column index of cell.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: