| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
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.
I think this youtube video might help https://www.youtube.com/watch?v=IRwVmTmN6go
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)
Easier dp. quite similar Uva problem: 10003.
Can this be solved using greedy?
No. Refer CLRS's algorithm book.