How can i convert the recursive function to count the number of paths having the maximum sum to its equivalent Dynamic Programming

help
1

Recursive function which i wrote is working fine except it takes more running time for large input size.So i need this to be optimised using dynamic programming.

int maxcountPath(int i,int j,int c)
{
int cell_value = a[i][j]-‘0’;

if (!isvalidate(i,j,c))
	return 0;

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

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

if(i==0) 
	return maxcountPath(i,j-1,c-cell_value);
  
else if(j==0) 
	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);

}

2

In general there are two important points that distinguish recursion from dynamic programming.

First recursion is top-down (starting with the big instances, by decomposing them into smaller instances and combining the answers) while DP is bottom-up (first solving the small cases, and combining them into larger ones).

The second important point is the table that contains the solutions to instances with certain parameters. This is to avoid computing certain cases more than once (as recursion tends to do).

So DP is upside down recursion in general. But one can also start with recursion and a lookup table that tests whether a certain subproblem was already solved.

So here you can use a 2d table which will contain the result for any (i,j).Now before calling the the func. look in your 2d table and if it is calulated simply return otherwise make the reccursive call and store the result in your table.
take a look here for more clarification

1 Like
3

I have tried to convert it to DP,but was getting incorrect output.Please help to figure out the logic that is missing in my code.

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;

}