14,209,828 members
Rate this:
See more:
I wrote a dynamic programming for the function maxcountPath to find the number of paths having the maximum sum.But was getting incorrect output

----------------------inputs------------------

```3
6
e 9 6 1 5 5
2 4 9 3 x 1
6 2 8 x 4 5
7 9 7 1 1 1
2 3 5 4 4 4
4 4 3 9 8 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```

----------------Expected outputs---------------------
```65 1
101 15
60 1```

What I have tried:

```#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;
}```
Posted
Updated 5 days ago
v3
Comments
Richard MacCutchan 5 days ago

Each of the recursive calls need to return their respective values, so the caller knows it is not complete.

Rate this:

## Solution 1

Quote:
How can i convert that recursive function to its Dynamic programming

First of all you need to understand what is Dynamic programming, and how it works.
Dynamic programming - Wikipedia[^]
Dynamic Programming - GeeksforGeeks[^]
Top 50 Dynamic Programming Practice Problems – Noteworthy - The Journal Blog[^]
Quote:
Tried to convert it to DP,but was getting incorrect output

I think you took a wrong approach by splitting the problem in 2 functions. Finding maximum count then counting paths that give arbitrary count, it is not the same as finding maximum count and counting paths the give maximum count.
Hints:
- Consider that every cell is the top left cell of a sub-rectangle that go to 'e' with same goal best score and number of path that lead to the score. When you know the answer for a sub rectangle, you don't need to explore it again, this is Dynamic programming.
- You also need to differentiate if a cell was already visited or not and if it is a dead end.
v3
Comments
BillWoodruff 5 days ago

+5 good resources !
Patrice T 5 days ago

Thank you
Rate this:

## Solution 2

Is it possible you are looking for an iterative solution ?

I suggest you start by understanding DP is recursion, but, bottom-up, not top-down. Your data/problem may not be suitable for a DP solution.

Good discussions to get an over-view: [^], and [^]

And, this MIT video a good resource: [^]
Comments
Diaesh Antony 5 days ago

This is the code i wrote with DP for maxcountPath(),but was getting incorrect ouput for finding number of paths having maximum sum

#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;
}
BillWoodruff 5 days ago

I suggest you edit your original post to show your latest code. Also, please tag the post to indicate you are working with C++.

There is a C/C++ forum here:

https://www.codeproject.com/Forums/1647/C-Cplusplus-MFC.aspx

Why not post there ?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 OriginalGriff 230 Dave Kreskowiak 185 Richard MacCutchan 150 Maciej Los 120 Thomas Daniels 110
 OriginalGriff 2,428 Richard MacCutchan 913 Thomas Daniels 785 Patrice T 739 Dave Kreskowiak 660

Advertise | Privacy | Cookies | Terms of Service
Web04 | 2.8.190617.3 | Last Updated 13 Jun 2019
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100