I am not being able to figure out the recursive solution for this dp problem

#1
#2

hello @nidhigupta847

it is simple .
let say solve(l) is the function that tells maximum number of segments of p,q,r.
then we have three options
a) we can break a length p from l and call the same function on remaining length l-p
b) we can break a length q from l and call the same function on remaining length l-q
c) we can break a length r from l and call the same function on remaining length l-r
whichever case will give maximum count we will pick that one.
solve(l) = 1(because we pick one rod) + max( solve(l-p) , solve(l-q) , solve(l-r) )

#3

int dp[10005];
//Complete this function
int rec(int n,int x,int y,int z)
{
if(n<0)
return 0;

if(dp[n]!=-1)
return dp[n];

if(n<min(x,min(y,z)))
{
    dp[n]=0;
    return dp[n];
}

dp[n]=max(max(rec(n-x,x,y,z),rec(n-y,x,y,z)),rec(n-z,x,y,z))+1;
return dp[n];

}
int maximizeTheCuts(int n, int x, int y, int z)
{
memset(dp,-1,sizeof(dp));
return rec(n,x,y,z);
}

I’m getting some test cases wrong

#4

I guess my base case is not correct

#5

@nidhigupta847

pls share ur code using cb ide

also if u r submitting it anywhere then share its link as well.

#6

It’s a test series so I can’t share the link

#7

ok , share ur code by saving it to cb ide

#8
#9

@nidhigupta847

yeah the base case was not correct.

u need to consider only those partition that are valid.

#10

Okay got it


Check this, its similar to what you did but I’m getting a TLE for this while your code got accepted why so ?

#11

it is giving tle becuase u r using -1 for invalid state use something else like -2 ,-3 or some other negative number.

we are using -1 to keep track of unvisited state so if we use -1 for invalid partition then it will not be possible to distinguish whether the state is unvisited or invalid and u will keep making call for invalid states (becuase it will treat it as unvisited) again n again that why tle

1 Like
#12

Oh yeah. Thanks man.