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.
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]
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.
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
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.
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.
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?
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.
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.
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.
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
