# Minimum Path Sum

Posted: 26 Dec, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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.
``````
``````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')