1. All the return statements in your function maxcountpath(...) assign a value to the local array countDP and then return that value. Since countDP will no longer be used after the return, the assignment is meaningless. You should therefore just return the assigned value instead!

2. Once you remove the assignments, you'll realize you are never using

`countDP`

. You can eliminate that array entirely.3. If this condition:

if(i==0 && j==0 && c== 0)is true, it means you can use 0 instead of i and j in the following branch. This simplifies the following if in such a way that you will realize it is always true.

4. You check two things at the same time: whether you've reached the starting point (0,0), and whether you've found a path with the right sum (c==0). This makes it harder to understand what happens for various combinations of these two conditions. You should split them into separate checks.

5. You repeatedly check whether your current cell is 'x'. Instead you could just check once and return - you can not take a path using this cell!

6. You repeatedly convert the numeric value of the cell a[i][j], which makes your code a bit harder to read. Just convert that value once and store it in a local variable.

7. It's a good idea to validate your input, but why do that repeatedly in every if branch? Do it right at the start of the function, once! Then you don't need to check later.

These things simplify your function to:

```
int maxcountPath(int i,int j,int c)
{
// have we gone outside the bounds?
if (!isvalidate(i,j,c))
return 0;
// after this point, you know your input is fine!
// has the recursion reached the starting point?
if(i==0 && j==0) // first part of your orginial check
{
if (c==0) // second part
return 1;
else // this is new! If c!=0, your path is not correct!
return 0;
}
// after this point, you know you're not at the starting point yet
// do we have a valid cell?
if (a[i][j] == 'x')
return 0; // you shall not pass!
// from this point we know we have a valid cell
// convert and store current cell value:
int cell_value = a[i][j]-'0';
if(i==0) // are we in first row?
return maxcountPath(i,j-1,c-cell_value);
else if(j==0) // are we in first column?
return maxcountPath(i-1,j,c-cell_value));
return maxcountPath(i,j-1,c-cell_value) +
maxcountPath(i-1,j,c-cell_value) + maxcountPath(i-1,j-1,c-cell_value);
}
```

On a sidenote, these simplifications (mostly the early returns) probably avoid the issue of i or j going below 0, therefore you can simplify your

`isvalidate()`

function to just check c. (and since c can only go out of bounds if you pass the wrong value from main(), you can probably remove that isvalidate() function entirely)
5

15

e 1 1 7 x 7 6 8 4 2 2 7 3 4 8

5 2 3 x 2 5 2 3 8 x 8 2 x 8 1

6 3 1 x 2 9 9 4 7 x 9 8 1 8 6

8 1 x x 9 x 8 6 3 5 2 x 4 9 4

5 5 3 5 5 9 x 3 8 9 3 1 1 x 5

3 6 1 1 x x 2 3 x 3 7 9 4 9 2

6 9 1 8 x x 5 3 2 1 2 9 x 7 x

4 1 x 1 8 1 2 9 6 5 6 1 1 x 2

x 6 4 3 9 2 5 x 7 x 2 8 6 x x

8 6 x x 7 1 3 8 x 5 3 x x 6 7

4 5 6 5 6 1 9 x 3 4 2 2 2 2 8

x 7 5 2 2 8 x x 4 5 3 5 8 x 1

9 5 9 5 x 4 8 3 x x 5 6 1 2 6

1 4 x x x x 4 3 2 1 5 8 2 x 4

6 5 2 7 4 6 4 7 3 x 4 8 x 7 s

9

e 4 x 9 1 7 5 9 1

2 9 8 2 9 6 x 8 8

9 5 9 5 7 1 x 2 1

2 3 8 9 x 3 8 7 8

8 8 9 2 x 2 7 8 2

4 6 2 6 8 7 9 5 9

x 6 3 8 8 3 5 8 7

9 5 7 3 5 8 4 8 1

x 4 4 5 8 7 4 1 s

7

e 2 8 7 6 7 4

2 6 6 2 x 6 7

3 1 1 4 x 7 2

1 4 2 6 1 7 6

x 7 8 9 x 4 x

7 1 1 4 x 2 4

8 6 5 9 1 1 s

7

e 5 4 9 9 3 7

x 3 1 4 5 7 5

3 6 3 x 6 x 5

7 1 5 8 x 9 1

8 4 3 9 6 8 3

2 x x 5 9 3 7

3 2 6 4 7 4 s

3

e 6 1

4 8 9

9 9 s

----------OUTPUT-------------------

143 ?

101 15

60 1

65 3

23 2

#include <string.h>

#include <stdlib.h>

char a[100][100];

int i,j,n,max_path_sum,max_path_count;

int isvalidate(int i, int j,int c)

{

if(i >= 0 && i < n && j>=0 && j<n &&="" c="">=0 && c <= max_path_sum)

return 1;

else

return 0;

}

int max(int a,int b, int c)

{

if(a >= b && a >= c)

return a;

else if(b >= a && b >= c)

return b;

else

return c;

}

/* Memoization approach to find the number of paths having the maximum sum */

int maxcountPath(int i,int j,int c)

{

int countDP[n][n][max_path_sum];

if(i==0 && j==0 && c== 0)

{

if(((a[i][j]-'0') - c) ==0)

return countDP[i][j][c] = 1;

else

return countDP[i][j][c] = 0;

}

if(i==0 && isvalidate(i,j,c) && a[i][j] != 'x')

return countDP[i][j][c] = maxcountPath(i,j-1,c-(a[i][j]-'0'));

else if(j==0 && isvalidate(i,j,c) && a[i][j] != 'x')

return countDP[i][j][c] = maxcountPath(i-1,j,c-(a[i][j]-'0'));

else if(isvalidate(i,j,c))

return countDP[i][j][c] = maxcountPath(i,j-1,c-(a[i][j]-'0')) +

maxcountPath(i-1,j,c-(a[i][j]-'0')) + maxcountPath(i-1,j-1,c-(a[i][j]-'0'));

else

return countDP[i][j][c] = 0;

}

/* DP approach to find the maximum sum path from top left corner to bottom right corner */

int maxsumPath(char a[][100], int n)

{

int maxpathDP[n][n];

for(i = 0; i < n; i++)

{

for(j = 0; j < n; j++)

{

maxpathDP[i][j] = 0;

}

}

for(i = 1; i < n; i++)

{

if(a[i][0] != 'x')

maxpathDP[i][0] = a[i][0]-'0' +maxpathDP[i-1][0];

else

break;

}

for(j = 1; j < n; j++)

{

if(a[0][j] != 'x')

maxpathDP[0][j] = a[0][j]-'0'+maxpathDP[0][j-1];

else

break;

}

for(i = 1; i < n; i++)

{

for(j = 1; j < n; j++)

{

if(a[i][j] == 'x')

{

continue;

}

else

{

if(a[i][j] == 's')

{

maxpathDP[i][j] = max(maxpathDP[i-1][j-1],maxpathDP[i-1][j],maxpathDP[i][j-1]);

}

else

{

maxpathDP[i][j] = a[i][j]-'0' + max(maxpathDP[i-1][j-1],maxpathDP[i-1][j],maxpathDP[i][j-1]);

}

}

}

}

return maxpathDP[n-1][n-1];

}

int main()

{

int t;

scanf("%d", &t);

while(t--)

{

scanf("%d", &n);

for (i = 0; i < n; i++)

{

for (j = 0; j < n; j++)

{

scanf(" %c", &a[i][j]);

}

}

max_path_sum = maxsumPath(a,n);

a[0][0] = '0';

a[n-1][n-1] = '0';

max_path_count = maxcountPath(n-1,n-1,max_path_sum);

if(max_path_count == 0)

{

max_path_sum = 0;

}

printf("%d %d\n",max_path_sum,max_path_count);

}

return 0;

}

won't even compile.