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.
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.We will Solve this problem using dynamic programming
public class MinimumPathSum {
public static void main(String[] args) {
int[][] arr = new int[][] {{1,3,1},
{1,5,1},
{4,2,1}};
System.out.println(CalculateMinimumPathSum(arr));
}
private static int CalculateMinimumPathSum(int[][] arr) {
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
if(i==0 && j == 0)
continue;
else if(i==0)
arr[i][j] = arr[i][j] + arr[i][j-1];
else if(j==0)
arr[i][j] = arr[i][j] + arr[i-1][j];
else
arr[i][j] = min(arr[i-1][j]+arr[i][j], arr[i][j-1]+arr[i][j]);
}
}
return arr[2][2];
}
private static int min(int i, int j) {
return i<j?i:j;
}
}
Output :
7
