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.

Thanks in advance!

Pretty standard dp problem. Try reading about optimal binary search tree. The recurrence for that problem is similar to this one.

Okay, so this can be solved via binary search too? I thought its a dp problem

He is talking about this.

This?

I think this youtube video might help https://www.youtube.com/watch?v=IRwVmTmN6go

Thanks, I will check it out.

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.

Thank for the list of resources, I will follow them one by one. Also, may I know, in which attempt you solved this question?

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)

That's Great, I will also keep practicing. :)

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?

Easier dp. quite similar Uva problem: 10003.

Can this be solved using greedy?

No. Refer CLRS's algorithm book.