Search This Blog

Friday, December 14, 2012

LeetCode:Minimum Path Sum

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.

public class Solution {
    public int minPathSum(int[][] grid) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[] row = new int[grid[0].length];
        
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(j>0)
                    row[j]=i>0?Math.min(row[j-1],row[j]):row[j-1];
                row[j]+=grid[i][j];
            }
        }
        return row[grid[0].length-1];
    }
}

No comments: