Click here to Skip to main content
14,209,828 members
Rate this:
Please Sign up or sign in to vote.
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:
Please Sign up or sign in to vote.

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:
Please Sign up or sign in to vote.

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)



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