# Help needed in finding no of path with min cost

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

I know youâ€™re trustworthy, but you should still give some semblance of a source

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

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

Wait, what? Wouldnâ€™t it be 0 + 1 + 0 + 1 + 0?

1 Like

Oh sorry

What should I change in code?

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

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;
}



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

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

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

Oh okay thanks a lot.