This dude is nostalgia. I still remember watching him when I was in the very lows of my life, struggling to even reverse an array and doubting myself whether I would make it into tech or not. Now after 2 yrs, I can proudly say that the impact his channel made in my self taught DSA journey is commendable. Thou many of this DP vids do not explain when for this subproblem we need the answer of this subproblem. but that's fine, since after I used to watch his solution I would go over it myself and try to figure out what happened in it. And maybe that's the reason of my sharpened DSA skills.
Thank you so much! You are helping me so much in my Algorithm's class with Rod-Cutting since my professor did a poor job in explaining it without going into detail. ♥
similar to knapsack I guess, rod length is the max capacity of knapsack and we've to maximize profit ie maximize items which we can put in the knapsack.
The question is incomplete without the cost of rod-piece of length 5,i.e. if we do not cut the rod. That's the reason when it is feeded in the code, it produces result 10 instead of 12.
This is pretty simple. Infact it is simply a different version of the 0/1 Knapsack Problem. Take the main length to be the weight of the bag and the weight of the difference smaller lengths as the weights of the different items and the prices and the values of the corresponding items.
Could you upload the video with stating reasons behind e.g. when you are at rod length 3(col) and cutting it into the length of 2( row 2) why are you going back to 2,1 and then adding the rate of length of rod 2? We can understand algorithm by looking at the code but the explanation should be of these small things about why we are doing that?
I know it's too too late to reply to your doubt, i am writing just to get myself a clarification as well , sothe reason to go back 'i' number of steps is : we try two possibilities 1. either cut the rod of current length 3 using 1 cuts (1lengthed cut 3 times),or 2. we can cut the rod of length 3 using 1cut and 2 cuts(1 + 2 = 3). going with 1st option we get profit = 2 + 2 + 2 (as length 1 has 2 as profit) , going with option 2 we get 5 + 2 as profit (5 being profit of length 2 cut and 2 being profit of length 1 cut). hence chose 7 over 6 from 2nd option(7).
further i would like to add Option 1 corresponds to exlude taking the element and option 2 corresponds to including taking the element hence rod cutting becomes a DP on subsequences problem(include / exclude principle problem)
The github algorithm function recursiveMaxValue does not work with the input used in the video. I used the array 2,5,7,8 and 4 as input. It gives the result 10 instead of 12 as per the video.
The explanation could have been more intuitive instead of saying "go here", "add this and that", "take max from this and that". Kindly remake the video explaining the concept in terms of array indices, the use of optimal substructure and overlapping subproblems. Appreciate your efforts though!
Hi thanks for the instruction. However, I'm having a question: When you go back to find the actual answer after filling the table. How would you consider all the possibilities that will make it to the length of 5, ? for example: in the video at length 5 and profit 12 you can cut 2, 3 OR 1,2,2, both will give you 12.
In 0/1 Knapsack, we can choose an item only once. For eg., if we take weight 5 in our knapsack we cannot consider it twice. But in rod cutting, we can make a cut twice or thrice depending upon the solution. If we are having a rod of length 7, then we can make 7 cuts of length 1.
Hi Tushar. I love your videos as does my entire algorithms class. Just a heads up: the more optimal implementation uses only O(B) space where B is the initial length of the rod. It is the same as for knapsack with repetition. T(b) = max(T(i-1, b-ai) + vi, T(i-1, b)) . You iterate through all the rod lengths for each entry and update the max. So it is still O(nB), but with improved space complexity. Cheers!
We can do this using a 1D DP array where best possible price for a rod of size n -> dp[n] = max(price[i] + dp[n - i - 1]) for all i= {0,1,....,n-1}. This would save space complexity. Implementation can be found here - www.geeksforgeeks.org/cutting-a-rod-dp-13/
Very nice tutorial. Crystal Clear explanation! Do you have any tips on how to 'word' the subproblems? In all your videos, the wording of the subproblems seems to be a very critical thing.
what if the profits are not increasing with increase in length, how to determine in a case when profits are random and not monotonically increasing or decreasing with the length size, in all your videos of this type of questions you have chosen the dataset where this algo fits in
+Vidur Chanana consider it like this: you have rod of length 3 and you can cut it in pieces of length 1 only. then you can make 3 cuts of profit 2 units each. hence 6 units of profit
+Mitali Varshney yepp got it. Thanks. I should have written one length instead of one way. then it would have made more sense. Anyways, Thanks for the help.
Thanks Tushar for explaining the problem and its solution. Great work! This problem seems to be similar to knapsack where in both cases we try to maximize our profit for a input range that we can select from to fill it upto a certain upper limit / value. However in case of knapsack, for a item 'i' weight (w[i]) which can be selected, when going back , we go back in the row above to the item being selected i.e T[i-1][j-w[i]] In this case, when we go back we seem to back in the same row i.e T[i][j-w[i]]. Can you please explain why this difference? In both the cases we try to pick a combination of values from the input range (either weight[] / rod length[]) at any time and not just consider individual items one at a time. Just thinking in both cases if there is any issue, in case if we do it consistently ?
Actually, I found a comment regarding the same question asked by some other person (Whizz Comp) in your Knapsack video. So basically, if there is infinite input range or there is repitition of values in input array - we can use : T[i][j-w[i]] + value[i] by going back in the same row but where there is no repitition of values we can use T[i-1][j-w[i]] + value[i] by going back in row above the item being selected. I found the answer there. Please ignore this one if you think above understanding is correct. Keep up the great work!.
I really liked ur video...btw i have seen this approach of getting answers by forming a 2-d array and 'doing the stuffs you did in this video '. I was wondering if there is a special name for this approach? when can we apply this method? (Is it applicable for this question only?)
+Tushar Roy Thanks! Tushar. Appreciating your efforts. Is there any other methods also available in DP other than top down and bottom up, If yes I think you can give quick demo on all this methods/approaches with use cases when to use what?
Hi Tushar , is the 2D array representation you have creadet in the wite bord for understanding only , since in the code github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CuttingRod.java i dont see any 2D array created.
You are right... we dont really need a matrix.. We just need two arrays.. The reason?.. In every step, we are using solution from previous row and the current row.. Hence, we only need two arrays..
Great videos Tushar. Can you make a video explaining how to design the algorithms you use... it would be a great help if you can do so before 1st december
What if there is no value in the market for a few lengths? For example, suppose the value for a rod with length 1 is 2, and the value for length 3 is 7 and a rod with length 2 is not defined. For this example we receive 2 arrays: cuts={1,3} and values={2,7}. In that case, in the formula instead of "if (j >= i)" we should have "if (j >= cut[i])" in which "cut" is one of the input arrays which represents valid cuts. Also val[i]+T[i][j-i]" should change to "val[i]+T[i][j-cut[i]]". Please correct me if I'm wrong.
This is not the best solution. You will have a running time of O(n^2) and use O(n^2) space, but if you you use a list instead of a 2D array, you will only use O(n) space.
Video is good.. But what is the lacking is the underlying explanation. You need to explain why you are using a matrix, not an array.. Also it requires explanation on why 1, 2, 3 are deducted while calculating the cost in each row of matrix.. the root explanation are as following 1) Matrix is used here because this dp problem requires two parameters.. i -> individual lengths in the rod, and l -> the length of rod.. If there was only one parameter, one dimensional array is enough 2) The reason why the numbers 1,2,3 are deducted in each step and why its compared with the value above is because of the recurrence relation of this problem. Basically, the relation is dp(i, l) = max of ( cost [i] + dp(i-1, l-i) , cost (i-1, l)) where dp(i,l) is the cost for a rod length l and with i units within the rod cost[i] -> cost of a unit. Just imagine about the last unit in the rod, length 4, cost 8.. If we take 4 units from the rod, the cost is 8.. hence 8 + dp(3, 5-4) If we do not consider 4 units, the cost would be dp(3, 5) Hence.. dp(i, l) will be max of ( 8 + dp(3, 1) , dp(3, 5)) Now, memoize this into a matrix.. and then look into this video.. you will understand.
The mechanics is: If you select the choice of cutting by 2 meters - then you go back 2 steps (because ur remaining length has reduced by two) If you select the choice of cutting by 3 meters - then you go back 3 steps (because ur remaining length has reduced by three) The intuition is: In every step you make a choice either to ignore the new way (and use above row) or by using the new way (and reduce length) and for the balance length using the pre-computed value - thats what happens here.
When he tries to check where he is getting the max value,If it isn't from above cutting configuration it implies that he had have cut the rod in the length of the current row ,so he counted the current row i.e. 2 in that step, than moved 2 steps back because the length of the rod is shorten by the values of current row(2 here), after that all follows recursively
bitbucket.org/anirbanhi/samplecodegit/src/master/com/apal/dynamicprogramming/CuttingRod.java The solution as explained in this video along with the table output.
Hi Tushar.. First of all thanx man. Ur tutorials are gr8. And thanks for you ur github contribution. For you RodCutting Solution Test case {3,5,8,9,10,20,22,25} the answer is 26. Can you explain how..? How is this rod partitioned.. ? And could you kindly provide code for rod splitup.?
Hey How is cutting rod is different from 0-1 knapsach in terms of method used to compute the optimal result? Same question for edit distance and LIS? Can we interchangeable use same code or is there any expectation case? Btw your lectures are very helpful :) Thanks in advance .
1. Can choose the item only once but more than 1 same lengths are possible, hence T[i][i-j] instead of T[i-1][i-j] 2. this is the starting problem. The cost in case of knapsack is only the weight which is also the case in this particular rod problem. Will be more tenuous if we add the cost of cutting to it. (i.e. max value with given weight and min. no of cuts). Hope it helps.
No recursion required when used array of objects. We have seen how recursion kills in high Fibonacci numbers.. I wish they also taught us DFS without recursion coz most of the graphs in real world are infinite. Here is C# solution without recursion github.com/jtambe/C-Sharp/blob/master/CuttingRod_Profit_Dynamic_Programming.cs
Hi can someone show how to draw such a 2D array fro the below problem Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.
This is the code in c++ for cutting rod problems .... nice lecture sir, thanks #include #include using namespace std; int cutting_road(int *cost_array, int size) { int *newarray = (int*)malloc(sizeof(int) * size + 1); newarray[0] = 0; int max_val = INT_MIN; for (size_t i = 1; i
Hi tushar, i just converted your sudocode in Java and which is better than your code on github, only thing is i used 2D array instead of overwriting into single array : ide.geeksforgeeks.org/Axo8yQ
If you are making a video on rod cutting problem without explaining an intuitive way of recursion, optimal substructure then there is no point posting it here.
This dude is nostalgia. I still remember watching him when I was in the very lows of my life, struggling to even reverse an array and doubting myself whether I would make it into tech or not. Now after 2 yrs, I can proudly say that the impact his channel made in my self taught DSA journey is commendable. Thou many of this DP vids do not explain when for this subproblem we need the answer of this subproblem. but that's fine, since after I used to watch his solution I would go over it myself and try to figure out what happened in it. And maybe that's the reason of my sharpened DSA skills.
Exactly watching detailed intuitions on TH-cam steals the chance of self analysis.
Life saver! I spent 3 hours trying to make a good guess and failed. Then I took 5 minutes to figure it out by watching your video. Thank you sir!
But your 3 hours matters if you tried hard.
Thank you so much! You are helping me so much in my Algorithm's class with Rod-Cutting since my professor did a poor job in explaining it without going into detail. ♥
similar to knapsack I guess, rod length is the max capacity of knapsack and we've to maximize profit ie maximize items which we can put in the knapsack.
Only difference is that the in 0/1 knapsack we cannot repeat a i length rod, once used before.
He is talking about Unbounded Knapsack
@@nilargharoy8810 yeah
Tushar you really are an amazing teacher!
The question is incomplete without the cost of rod-piece of length 5,i.e. if we do not cut the rod. That's the reason when it is feeded in the code, it produces result 10 instead of 12.
This is pretty simple. Infact it is simply a different version of the 0/1 Knapsack Problem. Take the main length to be the weight of the bag and the weight of the difference smaller lengths as the weights of the different items and the prices and the values of the corresponding items.
how about setting a manual camera focus instead of auto focus?
Could you upload the video with stating reasons behind e.g. when you are at rod length 3(col) and cutting it into the length of 2( row 2) why are you going back to 2,1 and then adding the rate of length of rod 2?
We can understand algorithm by looking at the code but the explanation should be of these small things about why we are doing that?
I know it's too too late to reply to your doubt, i am writing just to get myself a clarification as well , sothe reason to go back 'i' number of steps is :
we try two possibilities 1. either cut the rod of current length 3 using 1 cuts (1lengthed cut 3 times),or 2. we can cut the rod of length 3 using 1cut and 2 cuts(1 + 2 = 3).
going with 1st option we get profit = 2 + 2 + 2 (as length 1 has 2 as profit) , going with option 2 we get 5 + 2 as profit (5 being profit of length 2 cut and 2 being profit of length 1 cut). hence chose 7 over 6 from 2nd option(7).
further i would like to add Option 1 corresponds to exlude taking the element and option 2 corresponds to including taking the element
hence rod cutting becomes a DP on subsequences problem(include / exclude principle problem)
knapsack, coin, rod cut...all are similar problems.
And internally they have different types: 0/1 vs infinite, total number vs total value etc.
I really like this guys teaching.
I understand what dynamic programming is trying to do, but I do not get how to code it up
I don't quite understand why you do "two steps back" at around 6:00 - could you explain this in a bit more detail?
ok I see now, thank you
thanks man.. it was a really great video.. plz upload more
The github algorithm function recursiveMaxValue does not work with the input used in the video. I used the array 2,5,7,8 and 4 as input. It gives the result 10 instead of 12 as per the video.
Excellent description. Thank you.
For some reason I didn't understand any of this in class. Thanks sir.
very similar to 0/1 knapsack problem if we consider length as weight. The only difference is that we can use object of same weight many times.
The explanation could have been more intuitive instead of saying "go here", "add this and that", "take max from this and that". Kindly remake the video explaining the concept in terms of array indices, the use of optimal substructure and overlapping subproblems. Appreciate your efforts though!
seriously I wasnt able to understand as well :(
hope this video helps understand better th-cam.com/video/zFe-SX7jzDs/w-d-xo.html
This is similar to Coin change problem, where we can select the different length(change) to reach total length(sum)
Hi thanks for the instruction. However, I'm having a question:
When you go back to find the actual answer after filling the table. How would you consider all the possibilities that will make it to the length of 5, ? for example: in the video at length 5 and profit 12 you can cut 2, 3 OR 1,2,2, both will give you 12.
that y he said it is one of the possible ans
thanks a lot Tushar but on each DP solution you should explain subproblems
Thanks a lot for your time and efforts
***** when you say at 6:22 if( j >= i ) ;
do you mean j and i as counter ?
Like for( int i = 0 ; i < length; i++ ) and for( int j = 0; j
This Problem is just a 0/1 knapsack problem. Please current me if I wrong. and How it does differ.
In 0/1 Knapsack, we can choose an item only once. For eg., if we take weight 5 in our knapsack we cannot consider it twice. But in rod cutting, we can make a cut twice or thrice depending upon the solution. If we are having a rod of length 7, then we can make 7 cuts of length 1.
Hi Tushar. I love your videos as does my entire algorithms class. Just a heads up: the more optimal implementation uses only O(B) space where B is the initial length of the rod. It is the same as for knapsack with repetition. T(b) = max(T(i-1, b-ai) + vi, T(i-1, b)) . You iterate through all the rod lengths for each entry and update the max. So it is still O(nB), but with improved space complexity. Cheers!
We can do this using a 1D DP array where best possible price for a rod of size n -> dp[n] = max(price[i] + dp[n - i - 1]) for all i= {0,1,....,n-1}. This would save space complexity. Implementation can be found here - www.geeksforgeeks.org/cutting-a-rod-dp-13/
Max of what? You have written just one thing inside max
Very nice tutorial. Crystal Clear explanation!
Do you have any tips on how to 'word' the subproblems? In all your videos, the wording of the subproblems seems to be a very critical thing.
what if the profits are not increasing with increase in length, how to determine in a case when profits are random and not monotonically increasing or decreasing with the length size, in all your videos of this type of questions you have chosen the dataset where this algo fits in
thnx tushar for the great work... keep posting
+Tushar Roy How can you cut a length of rod 3 in one way and get 6 as the answer? Shouldn't it be 7? (At 2:03)
Thanks!
+Vidur Chanana consider it like this: you have rod of length 3 and you can cut it in pieces of length 1 only. then you can make 3 cuts of profit 2 units each. hence 6 units of profit
+Mitali Varshney yepp got it. Thanks. I should have written one length instead of one way. then it would have made more sense. Anyways, Thanks for the help.
Thanks , I am able to understand this
Y r u lying daaa
knapsack also works
cutting takes time and equipment that wears down so when the profit is equal, less cuts are preferred.
The assumption is that there is 0 cost involved for cutting the rod :)
here we assume that cutting takes no time as well as no wear and tear occurs to the equipments
it is also be done in O(n) of space complexity.................................
Thank you! it's really helpful.
Thanks Tushar for explaining the problem and its solution. Great work!
This problem seems to be similar to knapsack where in both cases we try to maximize our profit for a input range that we can select from to fill it upto a certain upper limit / value.
However in case of knapsack, for a item 'i' weight (w[i]) which can be selected, when going back , we go back in the row above to the item being selected i.e T[i-1][j-w[i]]
In this case, when we go back we seem to back in the same row i.e T[i][j-w[i]].
Can you please explain why this difference? In both the cases we try to pick a combination of values from the input range (either weight[] / rod length[]) at any time and not just consider individual items one at a time.
Just thinking in both cases if there is any issue, in case if we do it consistently ?
Actually, I found a comment regarding the same question asked by some other person (Whizz Comp) in your Knapsack video.
So basically, if there is infinite input range or there is repitition of values in input array - we can use : T[i][j-w[i]] + value[i] by going back in the same row
but where there is no repitition of values we can use T[i-1][j-w[i]] + value[i] by going back in row above the item being selected.
I found the answer there. Please ignore this one if you think above understanding is correct. Keep up the great work!.
Nice explanation! it helped me a lot :)
Man you wrong on the cut = 2. the optimal for up to size 2 is 5 not 4.
I really liked ur video...btw i have seen this approach of getting answers by forming a 2-d array and 'doing the stuffs you did in this video '. I was wondering if there is a special name for this approach? when can we apply this method? (Is it applicable for this question only?)
+Tushar Roy Thanks! Tushar. Appreciating your efforts. Is there any other methods also available in DP other than top down and bottom up, If yes I think you can give quick demo on all this methods/approaches with use cases when to use what?
Hi Tushar , is the 2D array representation you have creadet in the wite bord for understanding only , since in the code github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CuttingRod.java i dont see any 2D array created.
You are right... we dont really need a matrix.. We just need two arrays.. The reason?.. In every step, we are using solution from previous row and the current row.. Hence, we only need two arrays..
Great videos Tushar. Can you make a video explaining how to design the algorithms you use... it would be a great help if you can do so before 1st december
What if there is no value in the market for a few lengths? For example, suppose the value for a rod with length 1 is 2, and the value for length 3 is 7 and a rod with length 2 is not defined. For this example we receive 2 arrays: cuts={1,3} and values={2,7}. In that case, in the formula instead of "if (j >= i)" we should have "if (j >= cut[i])" in which "cut" is one of the input arrays which represents valid cuts. Also val[i]+T[i][j-i]" should change to "val[i]+T[i][j-cut[i]]". Please correct me if I'm wrong.
I totally agree with the formula....i is an index and one less than the rod length....the final formula in the video is not correct
Why the screen will be blur in several times?!!
Wouldn't this be a knapsack problem? Where length is your container?
This is not the best solution. You will have a running time of O(n^2) and use O(n^2) space, but if you you use a list instead of a 2D array, you will only use O(n) space.
+Dariush MJ where can i find it?
+Dariush MJ Do you mean use a list, and then change the list in each iteration? Is that how you would implement it? hmmm....
th-cam.com/video/ElFrskby_7M/w-d-xo.html
Video is good.. But what is the lacking is the underlying explanation. You need to explain why you are using a matrix, not an array.. Also it requires explanation on why 1, 2, 3 are deducted while calculating the cost in each row of matrix.. the root explanation are as following
1) Matrix is used here because this dp problem requires two parameters.. i -> individual lengths in the rod, and l -> the length of rod.. If there was only one parameter, one dimensional array is enough
2) The reason why the numbers 1,2,3 are deducted in each step and why its compared with the value above is because of the recurrence relation of this problem.
Basically, the relation is
dp(i, l) = max of ( cost [i] + dp(i-1, l-i) , cost (i-1, l))
where dp(i,l) is the cost for a rod length l and with i units within the rod
cost[i] -> cost of a unit.
Just imagine about the last unit in the rod, length 4, cost 8.. If we take 4 units from the rod, the cost is 8.. hence 8 + dp(3, 5-4)
If we do not consider 4 units, the cost would be dp(3, 5)
Hence.. dp(i, l) will be max of ( 8 + dp(3, 1) , dp(3, 5))
Now, memoize this into a matrix.. and then look into this video.. you will understand.
What is the significance of moving back n steps at each nth row iteration ?
The mechanics is:
If you select the choice of cutting by 2 meters - then you go back 2 steps (because ur remaining length has reduced by two)
If you select the choice of cutting by 3 meters - then you go back 3 steps (because ur remaining length has reduced by three)
The intuition is:
In every step you make a choice either to ignore the new way (and use above row) or by using the new way (and reduce length) and for the balance length
using the pre-computed value - thats what happens here.
Thanks for this explanation
At the end, he is asking where is this 12 coming from in the second row? Can you tell why did he move to left and counted 2?
When he tries to check where he is getting the max value,If it isn't from above cutting configuration it implies that he had have cut the rod in the length of the current row ,so he counted the current row i.e. 2 in that step, than moved 2 steps back because the length of the rod is shorten by the values of current row(2 here), after that all follows recursively
bitbucket.org/anirbanhi/samplecodegit/src/master/com/apal/dynamicprogramming/CuttingRod.java
The solution as explained in this video along with the table output.
does the question or algorithm allow cutting the rod into multiple rods of same length?
i am not able to find this question any where , can any one help me
Hi Tushar.. First of all thanx man. Ur tutorials are gr8. And thanks for you ur github contribution. For you RodCutting Solution Test case {3,5,8,9,10,20,22,25} the answer is 26. Can you explain how..? How is this rod partitioned.. ?
And could you kindly provide code for rod splitup.?
Hi Tushar, can we get a different result, like with 2 and 3 also we will be getting the same result.
In this particular example, could we not split the length into n/2 pieces of length 2 and n%2 piece of length 1 ?
It is amazing :) Please tell the secret; what/where/whom you are referring? :) Very clear approach, Thanks!
Check an alternative of the rod cutting problem here th-cam.com/video/9EkZ2V7Tiew/w-d-xo.html
Thank u Sir. Saved my hours.
Hey
How is cutting rod is different from 0-1 knapsach in terms of method used to compute the optimal result?
Same question for edit distance and LIS?
Can we interchangeable use same code or is there any expectation case?
Btw your lectures are very helpful :)
Thanks in advance .
In 0-1 Knapsack you can choose any item only once, here you can cut same length for infinite times
1. Can choose the item only once but more than 1 same lengths are possible, hence T[i][i-j] instead of T[i-1][i-j]
2. this is the starting problem. The cost in case of knapsack is only the weight which is also the case in this particular rod problem. Will be more tenuous if we add the cost of cutting to it. (i.e. max value with given weight and min. no of cuts). Hope it helps.
Why are you going 2 steps back and then comparing max? I couldn't understand
thanks for video sir
No recursion required when used array of objects. We have seen how recursion kills in high Fibonacci numbers.. I wish they also taught us DFS without recursion coz most of the graphs in real world are infinite.
Here is C# solution without recursion
github.com/jtambe/C-Sharp/blob/master/CuttingRod_Profit_Dynamic_Programming.cs
Thank you. Tushar
Sir, you are wrong on optimal up to size of 2: it should be 5 not 4
typical backpack type problem
I don’t get it....
Exam in few hours. Here for last minute revision.
Hi can someone show how to draw such a 2D array fro the below problem
Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.
🔥🔥🔥🔥🔥🔥🔥🔥
Where is your 2D array solution as u explained??????
I just wrote one.
bitbucket.org/anirbanhi/samplecodegit/src/master/com/apal/dynamicprogramming/CuttingRod.java
This is the code in c++ for cutting rod problems .... nice lecture sir, thanks
#include
#include
using namespace std;
int cutting_road(int *cost_array, int size)
{
int *newarray = (int*)malloc(sizeof(int) * size + 1);
newarray[0] = 0;
int max_val = INT_MIN;
for (size_t i = 1; i
sir plz upload your complete video on youtube..plz.
i am facing some problem to be there at your github link
Thank you!
isnt this exactly similar to 0-1 knapsack
video quality not good mr. ttuuusharr
soln is different and soln link is different he is high
this is 0 1 take or leave ?
I mean this problem like 0 1 knapsack
0 1 mean take or leave 1 if I take Item else 0 google it and your video is very good :))
***** I mean this is A binary choice(0 1) take Rod or Leave it
Thanks sir
Hi tushar, i just converted your sudocode in Java and which is better than your code on github, only thing is i used 2D array instead of overwriting into single array : ide.geeksforgeeks.org/Axo8yQ
make your video as well as explanation more clearly so it is easily understood...!!!!!!
Great
If you are making a video on rod cutting problem without explaining an intuitive way of recursion, optimal substructure then there is no point posting it here.
damnn!!
Use rupee instead of doller.
Buy you a new camera please
really not very poor in explaining
ur mom also won't understand
bro are u an Indian?
U destroyed the explanation! Are u making the video for urself???
Would you mind watching this video of Rod cutting problem and provide your review? th-cam.com/video/9EkZ2V7Tiew/w-d-xo.html
It's a discrete knapsack with recurring elements! Worst explanation ever.
very bad explanation. Not at all useful
That was totally boring
great presenter. bad camera work.
Not quite clear explanation.. So clumsy
Check the explanation out here th-cam.com/video/9EkZ2V7Tiew/w-d-xo.html