Help needed in finding no of path with min cost

help
1

Given a matrix of size MxN whose elements are non-negative. Count number of paths to reach last cell M-1xN-1 to first cell 0x0 along with cost of path and cost of path should be optimal. We can move one unit down or one unit right at a time.

#include<bits/stdc++.h>
using namespace std;
#define R 4
#define C 4

int minCost(int cost[R][C], int m, int n)
{


	int tc[R][C];

	tc[0][0] = cost[0][0];

	for (int i = 1; i <= m; i++)
		tc[i][0] = tc[i-1][0] + cost[i][0];

	for (int j = 1; j <= n; j++)
		tc[0][j] = tc[0][j-1] + cost[0][j];

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			tc[i][j] = min(tc[i-1][j], tc[i][j-1]) + cost[i][j];

	return tc[m][n];
}
   int cnt[R+1][C+1];


int count_path(int cost[R][C], int val,int m,int n)
{
    if(val<0)
        return 0;
    if(m==0&&n==0)
    {
        if(val==cost[0][0])
           return 1;
        else
            return 0;    
    }
    if(cnt[m][n]==-1)
    {
        if(m==0)
            cnt[m][n]=count_path(cost,val-cost[m][n],m,n-1);
        else if(n==0)
            cnt[m][n]=count_path(cost,val-cost[m][n],m-1,n);
        else
            cnt[m][n]=count_path(cost,val-cost[m][n],m-1,n)+count_path(cost,val-cost[m][n],m,n-1);
    }
    return cnt[m][n];
}
int main()
{
   int cost[R][C] ={{4,7,8,6}, 
					{6,7,3,9}, 
					{3,8,1,2},
                    {7,1,7,3}}; 
   memset(cnt,-1,sizeof(cnt));
    int mincost = minCost(cost,R-1,C-1);
    int paths = count_path(cost,mincost,R-1,C-1);
    /*for(int i=0;i<R;i++)
    for(int j=0;j<C;j++)
    cout<<cnt[i][j]<<" ";*/
    cout<<"The no. of paths with minimum cost of "<<mincost<<" are "<<paths<<endl;
    return 0;
}

Function for finding min cost is right. There is some error in finding no of paths. If i don’t use memoization then it is giving me correct answer. Please help me in finding mistake
@everule1 @ssjgz @galencolin @vijju123

2

I know you’re trustworthy, but you should still give some semblance of a source :stuck_out_tongue:

3

It is not from ongoing contest. I was simply trying to find total no of paths after seeing this

4

Got it. Your mistake, then, is that checking if val < 0 is not enough in count_path. You need to check that val is equal to the shortest distance from (0, 0) to that cell. If you don’t, consider what happens on this test case:

0   2 100
1   0 2
100 1 0

The minimum distance is 2. (I think) your ordering will start at (2, 2). It will then move up a row to (1, 2), and since val would be exactly 0, you would continue to (1, 1). Now that position is marked as visited, but val is 0, so you’re basically trapped and will find exactly 0 paths. What you would want to do is to stop at (1, 2) since it’s suboptimal, backtrack to (2, 2) and move to (2, 1), which is optimal. Checking if val is equal to the shortest distance from (0, 0) should do exactly that.

1 Like
6

Wait, what? Wouldn’t it be 0 + 1 + 0 + 1 + 0?

1 Like
7

Oh sorry

8

What should I change in code?

9

You need to somehow store the tc array from minCost, then, in count_path, replace if (val < 0) with if (val != tc[m - 1][n - 1])

1 Like
10

What would be time comp for this

#include<bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
int cnt[R+1][C+1][100000];

int minCost(int cost[R][C], int m, int n)
{
int tc[R][C];
tc[0][0] = cost[0][0];
for (int i = 1; i <= m; i++)
		tc[i][0] = tc[i-1][0] + cost[i][0];
for (int j = 1; j <= n; j++)
		tc[0][j] = tc[0][j-1] + cost[0][j];
for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			tc[i][j] = min(tc[i-1][j], tc[i][j-1]) + cost[i][j];
return tc[m][n];
}

int count_path(int cost[R][C], int val,int m,int n)
{
    if(m<0 || n<0 || val<0)
        return 0;
    if(m==0&&n==0)
    {
        if(val==cost[0][0])
           return 1;
        else
            return 0;
    }
    if(cnt[m][n][val]==-1)
    cnt[m][n][val] = count_path(cost, val-cost[m][n], m-1, n) + count_path(cost, val-cost[m][n], m, n-1);
    return cnt[m][n][val];
}
int main()
{
   int cost[R][C] ={{4,7,8,6},
			{6,7,3,9},
			{3,8,1,2},
                    	{7,1,7,3}};
   memset(cnt,-1,sizeof(cnt));
   int mincost = minCost(cost,R-1,C-1);
   int paths = count_path(cost,mincost,R-1,C-1);

   cout<<"The no. of paths with minimum cost of "<<mincost<<" is "<<paths<<endl;
return 0;
}
11

There’s probably a case that makes that run in O(NM \cdot 10^5).

12

Why O(NMâ‹…10^5) ? I have doubt about 10^5.

13

Because that’s how far you memoize, and you have an array that big anyway (so memset will take that long)

14

Oh okay thanks a lot.