14,209,923 members
Rate this:
See more:
I have wrote a function using memoization to count the maximum number of paths having the maximum sum from top left to bottom right of a matrix.My code is working fine for all the testcases except the below case which is showing incorrect output.Can anyone please tell me the logic that is missing in my code?

```n-->15(size of matrix)
max_path_sum -->143(maximum sum from top left to bottom right)

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```

```#include <stdio.h>
#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;
}```

What I have tried:

Intially i was facing SIGSEGV which is fixed by validating the boundary conditions
Posted
Updated 5 days ago
v4
Patrice T 12-Jun-19 1:52am

What result do you get and what result do you expect ?
Diaesh Antony 12-Jun-19 3:34am

----INPUT-----
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
Patrice T 12-Jun-19 2:13am

Advice: show enough code so we can run it.
Diaesh Antony 12-Jun-19 3:32am

#include <stdio.h>
#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;
}
CPallini 12-Jun-19 7:28am

Please post the exact code. This line
`if(i >= 0 && i < n && j>=0 && j<n &&="" c="">=0 && c <= max_path_sum)`

won't even compile.

Rate this:

## Solution 4

Just some things to simplify your code and maybe make it clearer what is happening, and, more importantly, not happening:

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)
v2
Diaesh Antony 12-Jun-19 8:30am

Thanks for suggestion.
Recursion approach will work fine for small inputs, but it will take exponetial time if we have a very large input.How can i change this recursive approach to DP
Stefan_Lang 5 days ago

Initially I also thought to avoid the recursion, but then i realized that, for an input of size NxN, the maximum rexursion depth is only 2*N - that's not so bad for N<1000, although you may need to increase the program stack size.

If you want to avoid the recursion, I'd better post a separate solution with explanations for that, for better readability.
Diaesh Antony 5 days ago

Please explain the equivalent dynamic programming approach for the same recursion function.I tried to implement it using DP,but was getting incorrect output.

Rick York 5 days ago

One more suggestion : save the values in binary form, not ASCII. This way you don't have to convert them to their binary value so often. You can convert them once and store them like that. Since x is a special value you can save it in its binary form also which is 120 and that should probably get a constant definition. This means your values will range from 0 to 9 and then the X value, 120 - all in binary.
Diaesh Antony 5 days ago

I have improved recursion to memoization.How can i convert maxcountPath() to dynamic programming?

#include <stdio.h>
#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;
}

int maxcountPath(int i,int j,int c)
{
int countDP[n][n];
int cell_value = a[i][j]-'0';

if (!isvalidate(i,j,c))
return countDP[i][j] = 0;

if(i==0 && j==0)
{
if (c==0)
return countDP[i][j] = 1;
else
return countDP[i][j] = 0;
}

if (a[i][j] == 'x')
return countDP[i][j] = 0;

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

else if(j==0)
return countDP[i][j] = maxcountPath(i-1,j,c-cell_value);

return countDP[i][j] = maxcountPath(i,j-1,c-cell_value) +
maxcountPath(i-1,j,c-cell_value) + maxcountPath(i-1,j-1,c-cell_value);

}

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;
}
Diaesh Antony 5 days ago

I have wrote in Dynamic programming for the function maxcountPath()-A function to find the number of paths having the maximum sum.But i am getting incorrect output.Please help me to figure out the logical mistake

This the code i wrote with DP for
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char a[100][100];
int i,j,n,max_path_sum,val,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;
}

int maxcountPath(int n, int c)
{
int countDP[n][n];
memset(countDP, 0, sizeof(countDP));

countDP[0][0] = c;

for(i = 1; i < n; i++)
{
if(a[i][0] != 'x')
{
countDP[i][0] = countDP[i-1][0] - (a[i][0]-'0');
}
else
break;
}

for(i = 1 ; i < n; i++)
{
if(a[0][i] != 'x')
{
countDP[0][i] = countDP[0][i-1] - (a[0][i]-'0');
}
else
break;
}

for(i = 1; i < n; i++)
{
for(j = 1; j < n; j++)
{
if(a[i][j] != 'x')
{
val = a[i][j]-'0';
countDP[i][j] = (countDP[i-1][j]-val)-(countDP[i][j-1]-val)-(countDP[i-1][j-1]-val);
}
else
continue;
}

}

return countDP[n-1][n-1];

}

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,max_path_sum);

if(max_path_count == 0)
{
max_path_sum = 0;
}
printf("%d %d\n",max_path_sum,max_path_count);
}

return 0;
}
Stefan_Lang 4 days ago

As you might have noticed, posting code in a comment isn't a great idea! Unless you take special precautions, the formatting will be lost and special characters in your code will be converted into something else, making the code unreadable. Besides, the font size is just too small to comfortably read large sections of code here.

If you changed your original code, it would be easier if you just pointed out what you changed, and/or posted only the code you've changed. If you changed a lot, it would probably better to append it to your original question, using the green link [improve question] at the bottom right of the question. Then you can properly format it, and others will also see and be able to comment on it.

As for your question, your use of recursion _is_ Dynamic Programming. I'm not sure what you want to know.

As for your code, the function maxsumPath() doesn't correctly treat all cases. It is important _not_ to add the current value to the sum, if the adjacent cell you're looking at does not have a path leading to it! You've failed to check that. Example:
s 1 1 1
1 x x 1
1 x 9 1
1 1 1 e
At cell (2,2), you'd calculate a maxsum of 9, even though no path is leading from s to this cell. Then you'd get a maxpathsum of 10, which can not be obtained with any valid path!

Please note I've posted a non-recursive approach (solution 5). While not using recursion, it solves the problem by solving subproblems first, just like the recursive approach. It therefore fulfils the requirements for being DP.
Rate this:

## Solution 1

If you want people to look at your code, make it easy to read. That means that "lazy variable names" are a poor idea - and single character names are just that.
It means not writing code like "if (...) return 1; else return 0;"
It means documenting your code so people have some idea what you intended code to do.
It means explaining what you expected the code to do, and what exactly it id instead: "it didn't work" is a useless error report because it tells us nothing we didn't already know: if it worked you wouldn't be asking the question!
It means explaining what you have tried to find out what the problem is.

And most of all, it means understanding the development process ... Compiling does not mean your code is right! :laugh:
Think of the development process as writing an email: compiling successfully means that you wrote the email in the right language - English, rather than German for example - not that the email contained the message you wanted to send.

So now you enter the second stage of development (in reality it's the fourth or fifth, but you'll come to the earlier stages later): Testing and Debugging.

Start by looking at what it does do, and how that differs from what you wanted. This is important, because it give you information as to why it's doing it. For example, if a program is intended to let the user enter a number and it doubles it and prints the answer, then if the input / output was like this:
```Input   Expected output    Actual output
1            2                 1
2            4                 4
3            6                 9
4            8                16```
Then it's fairly obvious that the problem is with the bit which doubles it - it's not adding itself to itself, or multiplying it by 2, it's multiplying it by itself and returning the square of the input.
So with that, you can look at the code and it's obvious that it's somewhere here:
```int Double(int value)
{
return value * value;
}```

Once you have an idea what might be going wrong, start using the debugger to find out why. Put a breakpoint on the first line of the method, and run your app. When it reaches the breakpoint, the debugger will stop, and hand control over to you. You can now run your code line-by-line (called "single stepping") and look at (or even change) variable contents as necessary (heck, you can even change the code and try again if you need to).
Think about what each line in the code should do before you execute it, and compare that to what it actually did when you use the "Step over" button to execute each line in turn. Did it do what you expect? If so, move on to the next line.
If not, why not? How does it differ?
Hopefully, that should help you locate which part of that code has a problem, and what the problem is.
This is a skill, and it's one which is well worth developing as it helps you in the real world as well as in development. And like all skills, it only improves by use!
Rate this:

## Solution 3

Quote:
Can anyone please tell me the logic that is missing in my code?

I think your problem is that `maxsumPath` can take into account some impossible path.
You should print `maxpathDP` to see how you get the maximum path.

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
Rate this:

## Solution 5

As per request, here's how you need to go about to create a non-recursive solution:

There are probably many different approaches, but the easiest to explain in this context, is simply turning the recursion upside-down:

The recursion works by calculating the results for the smaller sized problem, and deriving the solution for the full-sized problem from that. The iterative solution reverts this approach, by solving the smallest size problems, and iteratively derive the solutions for the next larger sized problems. Obviously, you need to store the intermediate results somehow, and you need to make sure that you get all the smaller solutions that you need in the next step.

For this problem, the partial problems to solve iteratively are the maximum value and number of maximum paths from one of the end points to one position in the NxN matrix. To keep track of these two values, I'd suggest creating a simple struct. And to keep track of all partial solutions, I'd create a NxN array of these structs:
```struct sum_paths {
int sum;
int num_paths;
};
struct path_results {
int rows;
int columns;
sum_paths* results;// must be allocated dynamically (and released when done)

// get index for array element
int at (int row, int column)
{
return row*columns+column;
}

// set values at array position
void set_at(int row, int column, int sum, int npaths)
{
results[at(row, column)].sum = sum;
results[at(row, column)].num_paths = npaths;
}

// retrieve values at array position
sum_paths get_at(int row, int column)
{
return results[at(row, column)];
}
};```

You'll start in one corner - in the spirit of your recursive program that roots its recursion in the lower right corner, I'd suggest starting in the lower right corner. The maximum value to reach that position is 0, because there is no value assigned to this cell, and the number of paths is 1, so you assign (0,1) to the result array at position (N-1,N-1) :
```// allocate matrix for intermediate results
path_results results;
// to do: allocate results array

// set position at end of path
int row = N-1;
int column = N-1;

// initialize end of path (sum = 0 and num_paths = 1)
results.set_at(row, column, 0, 1);
```

Next you can derive the correct values for the bottom row, going right to left. You need to be careful that you should only set a value != 0 here if there is actually a path leading to the cell to your right, and the current cell is not blocked:
```for (column = N-2; column >= 0; --column)
{
int sum = 0;
int npaths = 0;
if (A[row][column] != 'x')
{
npaths = results.get_at(row, column+1).num_paths;
if (npaths > 0)
sum = A[row][column]-'0' + results.get_at(row, column+1).sum;
}
results.set_at(row, column, sum, npaths);
}
```

Next you continue from bottom to top and right to left, to fill in the results set. You have to be careful when checking and combining the results from the cells to your right, from below, and from the lower right: first you need to find out which path yields the maximum sum, and then you need to add the paths from each direction that does yield this result. And of course you always need to check whether there is a valid path in either direction to start with.

Eventually your process will reach cell [0][0], and you can print out the result.

I'll leave the details of the implementation as an exercise for you. If you don't get the result 4, I suggest that you use the debugger on the last example to find out what is going wrong. (and yes, the fact that I know the result means I do have a working program - but you really should try this on your own)

P.S.:
Here's the code I used to print out not only the final result, but also the entire array of intermediate results. I've found it rather helpful to locate some subtle bugs I've introduced in early versions of my code. You might find it helpful, too:
```for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j)
cout << results.get_at(i, j).sum << ' ';
cout << endl;
}
cout << endl;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j)
cout << results.get_at(i, j).num_paths << ' ';
cout << endl;
}
cout << endl;
cout << "maximum sum: " << results.get_at(0,0).sum << endl;
cout << "number of paths: " << results.get_at(0,0).num_paths << endl;
```
v2

Top Experts
Last 24hrsThis month
 OriginalGriff 210 Dave Kreskowiak 195 Richard MacCutchan 140 Maciej Los 120 Thomas Daniels 90
 OriginalGriff 2,428 Richard MacCutchan 913 Thomas Daniels 785 Patrice T 739 Dave Kreskowiak 660