Note: You can only move either down or right at any point in time.
Idea: Dynamic programming. Assume the F[i][j] is the minimum path sum from (i,j) to (m-1, n-1). Then we have the equation:
F[i][j]=grid[i][j]+Math.min(F[i+1][j], F[i][j+1]). The result is F[0][0].
Time: O(n^2) Space: O(n^2)
Code:
public class Solution{
public int minPathSum(int[][] grid) {
if(grid.length==0||grid[0].length==0)
return 0;
int[][] path=new int[grid.length][grid[0].length];
int m=grid.length;
int n=grid[0].length;
path[m-1][n-1]=grid[m-1][n-1];
for(int j=n-2;j>=0;j--)
path[m-1][j]=grid[m-1][j]+path[m-1][j+1];
for(int i=m-2;i>=0;i--)
path[i][n-1]=grid[i][n-1]+path[i+1][n-1];
for(int i=m-2;i>=0;i--)
{
for(int j=n-2;j>=0;j--)
{
path[i][j]=grid[i][j]+Math.min(path[i+1][j],path[i][j+1]);
}
}
return path[0][0];
}
}
No comments:
Post a Comment