Rod cutting 2d dp approach

#1


sir i know that i am using lots of memory in this logic of mine… but for the learning purpose if i want to know am i implemeting the correct logic ar not and if not correct where am i wrong…
so can you please help me with that

#2

hello @Shobhit_kumar
what ur dp[i][j] is telling ?

#3

@Shobhit_kumar
this should be ur recurrence relation->
cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 … n-1}

later u can use dp array to memoise it

#4

sir yes i have used the approach you are telling me and got the right anwer from there too but here my dp[i][j] is telling maximum profit i can generate by selling the piece of length j-i and my final anwer would be dp[0][n] what is the flaw in this logic??

#5

effectively u want to store length(j-i) only so linear array for memoisation is sufficient where
dp[i] will tell maximum profit we can make from i length rod.

#6

yes sir that is complety fine but i just wanted to know that if i am going with that approach of mine so that will only give MLE and TLE or is the logic also wrong?? that’s my main concern…please elaborate on this

#7

pls share pure recursive code(no dp) with me.
i will check whether it will work or not

#8

https://ide.codingblocks.com/s/350643 here is the pure recursive code sir

#9

@Shobhit_kumar
ur logic is correct, there was some implementation issue check now->

#10

yes that worked thanks sir

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.