Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### m0ew's blog

By m0ew, history, 3 months ago, ,

Hi everyone, This is my first post.I was trying to solve the Road Cutting problem on interviewbit.com.

Here is the problem link — https://www.interviewbit.com/problems/rod-cutting/

I read the editorial as well but i wasn't able to understand it. Detailed approach to this problem is appreciated.

 » 3 months ago, # |   0 Pretty standard dp problem. Try reading about optimal binary search tree. The recurrence for that problem is similar to this one.
•  » » 3 months ago, # ^ |   -17 Okay, so this can be solved via binary search too? I thought its a dp problem
•  » » » » 3 months ago, # ^ |   -8 This?
 » 3 months ago, # |   +1 I think this youtube video might help https://www.youtube.com/watch?v=IRwVmTmN6go
•  » » 3 months ago, # ^ |   0 Thanks, I will check it out.
 » 3 months ago, # |   +3 Struggling with this type of problem for the first time is totally ok. I'm giving you a few resources that can help you. First of all, this problem can be solved easily with dynamic programming, so you have to read and understand dynamic programming properly. This problem falls under a classic dynamic programming section named matrix chain multiplication.
•  » » 3 months ago, # ^ |   0 Thank for the list of resources, I will follow them one by one. Also, may I know, in which attempt you solved this question?
•  » » » 3 months ago, # ^ |   0 It was a very familiar problem to me because I solve many problems on MCM dp ( matrix chain multiplication). So this time no significant time needed (Don't get frustrated seeing this, if you practice enough you will feel the same)
•  » » » » 3 months ago, # ^ |   0 That's Great, I will also keep practicing. :)
•  » » 4 weeks ago, # ^ |   0 I'm also struggling on the same problem. The problem is similar to MCM but we've been asked to return the array of elements instead of final cost. Storing the values(3-D vector) may be one approach to solve the problem. Is there a way to create the path using only cost matrix?
 » 3 months ago, # |   0 Easier dp. quite similar Uva problem: 10003.