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.
Example:
Solution
Its a DP problem, Maintain previous states which gives minimum distance, Calculate current state based on the previous state.
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
public class MinimumPathDistance { public int minPathSum(int[][] grid) { int n = grid.length, m = grid[0].length; int[][] dp = new int[n][m]; dp[0][0] = grid[0][0]; for (int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int j = 1; j < m; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[n - 1][m - 1]; } public static void main(String[] args) { int [][] grid={ {1,3,1}, {1,5,1}, {4,2,1} }; System.out.println(new MinimumPathDistance().minPathSum(grid)); } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.