Minimum Path Sum

Posted: 26 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninjaland is a country in the shape of a 2-Dimensional grid 'GRID', with 'N' rows and 'M' columns. Each point in the grid has some cost associated with it.

Find a path from top left i.e. (0, 0) to the bottom right i.e. ('N' - 1, 'M' - 1) which minimizes the sum of the cost of all the numbers along the path. You need to tell the minimum sum of that path.

Note:
You can only move down or right at any point in time.
Input format :
The first line contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains two space-separated integers 'N' and ‘M’ representing the number of rows and number of columns in the grid, respectively. 

Next 'N' lines will have 'M' space-separated integers, each line denotes cost values of that row.
Output format:
For each test case, print the minimum sum of the path from top left to bottom right.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Follow Up:
Can you solve this in O(1) space complexity?
Constraints:
1 <= T <= 100   
1 <= N, M <= 10^2
1 <= GRID[i][j] <= 10^5

Where 'GRID[i][j]' denotes the value of the cell in the matrix.

Time limit: 1 sec
Approach 1

The main idea is to use recursion to reduce the big problem into several smaller subproblems.

 

  1. We will call a minSumHelper function that returns us the minimum Sum path from the current point to destination ('N' - 1, ‘M’ - 1).
  2. From each point ('i' , ‘j’), we have 2 choices:
    • We can move right to ('i' , ‘j’ + 1). Then we will do a recursive call with ('i' , ‘j’ + 1) as our starting point, say the sum from this call comes out to be ‘A’.
    • Or we can move down to ('i' + 1 , ‘j’). Then we will do a recursive call with ('i' + 1, ‘j’) as our starting point, say the sum from this call comes out to be ‘B’.
    • Then our minimum cost from ('i' , ‘j’) to ('N' - 1,'M' - 1) will be 'GRID[i][j]' + min('A','B').
  3. The algorithm for minSumHelper will be as follows:
    • Int minSumHelper('GRID', ‘i’, ‘j’, ‘N’, 'M)
      • If ‘i’ >= ‘N’ or ‘j’ >= ‘M’ :            , if the point is out of grid.
      • return INT_MAX
      • If  ‘i’ == ‘N’ - 1 and j == ‘M’ - 1:
      • return ‘GRID[i][j]’.
      • Int ‘A’ = minSumHelper('GRID', 'i', 'j' + 1, ‘N’, ‘M’)
      • Int 'B' = minSumHelper('GRID', ‘i’ + 1, ‘j’, ‘N’, ‘M’)
      • return 'GRID[i][j]' + min('A','B')
Try Problem