Wednesday, February 12, 2014

LeetCode: 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.

Solution:

public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid.length == 0 || grid[0].length==0)
            return 0;
        for(int row = 0; row<grid.length; row++)
        {
            for(int col=0; col<grid[0].length; col++)
            {
                if (col>0 && row>0)
                    grid[row][col] += Math.min(grid[row][col-1], grid[row-1][col]);
                else if (col>0)
                    grid[row][col] += grid[row][col-1];
                else if (row>0)
                    grid[row][col] += grid[row-1][col];
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

No comments :

Post a Comment