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

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

2022-05-01

204

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:

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:

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.

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-05-01

need an explanation for this answer? contact us directly to get an explanation for this answer

1) Using dynamic programming

We will create a cost[m][n] matrix for storing the cost of visiting the cell, visiting the grid[0][0] 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[0][j]=cost[0][j-1]+grid[0][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][0]=cost[i-1][0]+grid[i][0] 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]

Pseudo Code:

int findsum(grid[m][n])
	if(m==0 and n==0)
		return 0
	else
		for(row=0;row<m;row++)
			for(col=0;col>n;col++)
				if(row==0 and col==0)
					cost[row][col]=grid[row][col]
				if(row==0)
					cost[row][col]=cost[row][col-1]+grid[row][col]
				if(col==0)
					cost[row][col]=cost[row-1][col]+grid[row][col]
				else
					cost[row][col]=min(cost[row-1][col],cost[row][col-1])+grid[row][col]

Time Complexity: O(m*n)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test case: ";
    cin >> t;

    while (t--) {
        ll m, n;

        cout << "Enter number of rows and columns: ";
        cin >> m >> n;

        ll dp[m][n], dp1[m][n];

        cout << "Enter elements: ";
        for (ll i = 0; i < m; i++)
            for (ll j = 0; j < n; j++)
                cin >> dp[i][j];

        for (ll i = 0; i < m; i++) {
            for (ll j = 0; j < n; j++) {
                if (i == 0 and j == 0)
                    dp1[i][j] = dp[i][j];
                else if (i == 0 and j != 0)
                    dp1[i][j] = dp1[i][j - 1] + dp[i][j];
                else if (j == 0 and i != 0)
                    dp1[i][j] = dp1[i - 1][j] + dp[i][j];
                else
                    dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + dp[i][j];
            }
        }
        
        cout << "Minimum Cost: ";
        cout << dp1[m - 1][n - 1] << "\n";
    }
    return 0;
}

Output

Enter number of test case: 2
Enter number of rows and columns: 3 3
Enter elements: 1 3 1
1 5 1
4 2 1
Minimum Cost: 7
Enter number of rows and columns: 4 4
Enter elements: 1 3 5 2
3 4 7 2
4 5 2 8
4 5 9 1
Minimum Cost: 22

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.

Pseudo Code:

findsum(grid[m][n])
	cost[m][n]
	for(row=0;row<m;row++)
		for(col=0;col<n;col++)
			cost[row][col]=INFINTE
		
	cost[0][0]=grid[0]][0]
	queue<pair<int,int>> q
	q.push({0,0})
	dx[]={0,1}
	dy[]={1,0}
		
	while(!q.empty())
	{
		pair<int,int> p=q.front()
		q.pop()
		x=p.first
		y=p.second
		for(i=0;i<2;i++)
		{
			a=x+dx[i],b=y+dy[i]
			if(a>=0 and a<m and b>=0 and b<n and cost[a][b]>cost[x][y]+grid[a][b])
			{
				q.push({a,b})
			cost[a][b]=cost[x][y]+grid[a][b]
			}
		}
	}

Time Complexity: O(n*m)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter the number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter numbe of rows and columns: ";
        ll n, m;
        cin >> n >> m;

        ll grid[n][m];
        ll cost[n][m];

        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++) {
                cin >> grid[i][j];
                cost[i][j] = INT_MAX;
            }

        cost[0][0] = grid[0][0];
        queue<pair<ll, ll> > q;
        q.push({ 0, 0 });
        ll dx[] = { 0, 1 };
        ll dy[] = { 1, 0 };

        while (!q.empty()) {
            pair<ll, ll> p = q.front();
            q.pop();
            ll x = p.first;
            ll y = p.second;
            for (ll j = 0; j < 2; j++) {
                ll u = x + dx[j];
                ll v = y + dy[j];
                if (u >= 0 and u < n and v >= 0 and v < m and cost[u][v] > cost[x][y] + grid[u][v]) {
                    cost[u][v] = cost[x][y] + grid[u][v];
                    q.push({ u, v });
                }
            }
        }

        cout << "Minimum Cost: ";
        cout << cost[n - 1][m - 1] << "\n";
    }
    return 0;
}

Output

Enter number of test case: 2
Enter number of rows and columns: 3 3
Enter elements: 1 3 1
1 5 1
4 2 1
Minimum Cost: 7
Enter number of rows and columns: 4 4
Enter elements: 1 3 5 2
3 4 7 2
4 5 2 8
4 5 9 1
Minimum Cost: 22

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)