Dynamic Programming: the Rod Cutting Problem

Table of Contents:

00:00 - Introduction and Prerequisites
00:19 - Rod Cutting Problem Definition
00:36 - Dynamic Programming Template
01:02 - Recursive Solution Design
04:02 - Recursive Solution
05:02 - Recursive Tree
05:56 - Parameter Analysis
06:19 - Memoized, Top-Down Dynamic Program
06:49 - Memoized Tree
07:35 - Iterated, Bottom-Up Dynamic Program
08:27 - Reconstructing the Optimal Cuts
09:19 - Wrap-Up

Thanks to Cydni Turner for noticing a really bad cut-and-paste error on a previous version (which caused me to republish this version), and to Saniya Godil for noticing that I didn't initialize everything, luckily getting that fix in time for this version too.

[konstantinrebrov]

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.

[wollebeck]

Really great explained! Enjoyed "the voice from above"

[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

[bertrandpinet]

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

[brianheartwood]

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

[rajeshranjan]

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

[wrenmoniker]

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?

[Anthony-cuot]

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

[gabrielalvarez]

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.

[christofu_]

Don't you only have to iterate over half the rod length because there will be redundancies with symmetrical cuts? I.E if you had a rod of length 10, it would be redundant to check cuts (3, 7) and (7, 3) as the result would be the same?

[DrMerlin]

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] <= Table[i]?

[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 <= n; ++length){
for(int i = 1; i<= length; ++i){
table[length] = Math.max(table[length], price[i] + table[length - i]);
}
}
return table[n];
}

So in this line we do not need to do the recursive call.

table[length] = Math.max(table[length], price[i] + table[length - i]);

[RafaelNascimento-qojp]

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