Dynamic Programming: the Rod Cutting Problem

[@mopedg8962]

Really great explained! Enjoyed "the voice from above"

[@konstantinrebrov675]

Wow, it's a very unique insight for dynamic programming, that it's actually originally a recursive problem that can be represented as recursion tree. And then we optimize it.

[@bablobko]

Thanks a lot for the video. Great help to all of us. Please carry on. We are indebted.

[@janpoonthong]

I like the tree visualization, super helpful

[@brianheartwood2071]

I lolled at the voice. thanks man this was informative and great.

[@bertrandpinet5782]

Awesome ! You are so much talented at teaching, thank you and please keep going =)

[@ashishmore5549]

Thank you Sir Great Explanation

[@David-zv5kw]

Thank you Sir! Very helpful!

[@Anthony-cu3ot]

Hi, first awesome video ! Secondly, I haven't quite understood why you are calling RodCutting(length-i, Price) and not RodCutting(length-i, Price, Table) at 6:47. Am I missing something ? Thanks for your awesome work tho

[@AlgorithmswithAttitude]

That is a cut-and-paste error. It should have Table.

[@omarmohamed3473]

perfect explaination

[@balaeinstein8710]

thanks a lot sir. you are back again

[@AlgorithmswithAttitude]

I actually posted this video a couple of months ago, but last week someone pointed out that there was an error on one of the later slides. It seemed serious enough for me to fix it and repost it.

[@gabrielalvarez4491]

Which package are you using to display pseudocode (the one shown in 06:46). Lately, I've been using the "algorithmic" package which I've found really useful because it highlights some usual keywords such as "for ... to", "while", "return" "if" "else" "loop ... until". Did you know that package? If so what were the reasons that made you not to use it? Thanks for sharing knowledge in such an organized and entertaining way.

[@AlgorithmswithAttitude]

I'm just tabbing, maybe I'll check that package out in the future.

[@DrMerlin62]

In the iterative solution why do we set tmp = Price[i] + Table[length - i]? Why not tmp = Table[i] + Table[length - i] instead? I don’t understand why we fix the value of the first cut instead of looking up the maximum value for that first cut from our lookup table. Isn’t Price[i]

[@AlgorithmswithAttitude]

There are multiple ways to find the correct answer. Your formula will also find it. After finding the optimal amount , if you then want to reconstruct what the best cuts are, it is slightly more direct to know what the first cut is, and take that piece whole, rather than making a cut and then recursively having to cut each of those two parts...but if you start from small i values, and keep the first i value that you find in case of ties, it should be that you end up finding an I such that price[i] == table[i], so it makes no real difference.

[@DrMerlin62]

@@AlgorithmswithAttitude thank you for the explanation! Loved the video!

[@wrenmoniker6137]

I'm a little confused as to why at 5:43 the cost from 5 to the answer node is 14 even though the table says it's worth 12 dollars. Same with node 4 with a cost of 10, but it says 11. Is this a typo or am I missing a calculation?

[@AlgorithmswithAttitude]

The table has the prices for a single rod. So, the store sells a length 5 rod for 12, and they sell a length 4 rod for 10. The algorithm is calculating how much you can get for that same length rod, if you are willing to cut it. For the length 4 rod, you can sell a length 3 rod for 9 and a length 1 rod for 2, for 11 total. For the length 5 rod, you can sell a length 3 rod (9) and a length 2 rod (5) for 14 total. The algorithm is calculating those numbers, given the numbers in the table.

[@rajeshranjan1406]

price must be price[i-1] instead of price[i] at 5:57

[@davidtaylor2809]

I think it is fine as is, I assume that the array has the sale price for length i at index i. I could have simplified the base case by starting max at 0, and getting rid of the first conditional, but usually only worry about clean up like that for the final version.

[@infodemicyar8712]

You're great!

[@RafaelNascimento-qo1jp]

recursion is scary, it seems like a kind of sorcery hahaha

[@AlgorithmswithAttitude]

Once you get it, it is really a powerful tool to approach a lot of different problems. But, wrapping your head around it is difficult to start. Which is why they say...if you want to understand recursion, first understand recursion.

[@ThuyNguyen-ss7ed]

i want to code. Do you have ?

[@AlgorithmswithAttitude]

Are you asking me for my code? Because that isn't the same thing as you coding if you want to code. And...my code for what? The rod cutting algorithm?

[@Kirbychu1]

nice

[@Rockyzach88]

Good

[@bablobko]

In the bottom up solution given at the time 8:31, you are making a recursive call, that we can avoid altogether. RodCutting(int n, int[] price[]){ { int[] table = new int[n + 1]; table[0] = 0; int tmp = 0; for(int length = 1; length

[@AlgorithmswithAttitude]

I am not sure what recursive call you are talking about? Do you mean the table look-up? The bottom up version has no recursive call.

[@ihsannuruliman3656]

what the heck, it's not recursive call