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.
Input starts with an integer T (≤ 100), denoting the number of test cases. Each case starts with an integer m and n (1 ≤ n,m ≤ 1000) denoting the number of rows and number of columns, followed by m rows having n columns as input.
Output the minimum sum to reach the end.
Example with explanation:
Input: T = 1 m = 3, n = 3 [1,3,1] [1,5,1] [4,2,1] Output: 7 Because the path 1→3→1→1→1 minimizes the sum.
1) Using dynamic programming
We will create a cost[m][n] matrix for storing the cost of visiting the cell, visiting the grid will cost the same, visiting the cell at the first row will only consider the cost of visiting the current cell cost plus the upto the last visited cell that is cost[j]=cost[j-1]+grid[j], similarly the cost of visiting the last column will cost the current grid value plus the cost upto the cell before it that it cost[i]=cost[i-1]+grid[i] and the rest of the cell will cost the min of cost coming from left or cost coming from top that is cost[i][j]=min(cost[i][j-1],cost[i-1][j])+grid[i][j]
Time Complexity: O(m*n)
2) Using graphical approach
Initially, we will declare the cost of visiting the cell as INFINITE then
we will use relaxation principal, that is if the cost of visiting the cell plus the distance of the previous cell is smaller than the current cell cost we will update the cost and we keep on doing it until we get the minimum cost.
we will use queue with pair to use the index of visited cell or unvisited cell, similar to level order traversal approach.
Time Complexity: O(n*m)
Outputneed an explanation for this answer? contact us directly to get an explanation for this answer