DP 50. Minimum Cost to Cut the Stick
Vložit
- čas přidán 18. 04. 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3rWLMnC
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the MCM Dp, this is the first problem on the pattern Partition DP.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
After getting this far in this DP series, I can say that I am starting to get ideas before you explain them. Thank you, Striver. You're the best teacher.
I don't know why but...
MCM and this Video it feels like I am just seeing and memorising the solution..
Maybe Partition DP is not for me... And I was thinking to Learn digit dp.. lol 😂
same situation😂
Whats the situation of you guys now ?
@@pqrstwxyz1175 hows urs?
@@pqrstwxyz1175 whats your situation now?
u did great exaplantion, learned a lot, if u set j = i in j loop, then u don't need to check if (i < j), just share my thought
Yes, I also observed this
00:00 Find the minimum cost to cut a stick given a cuts array and length of the stick.
04:07 The video sponsor is HyreX, an app for finding startups to work for.
07:55 To solve the problem independently, the array must be sorted.
11:46 Algorithm to find minimal cost for stick cutting
15:36 Algorithm for finding minimal cost partition
19:16 Explanation of how to get the length of a stick easily
22:46 Tabulation is the way to optimize the time complexity of the algorithm.
26:39 Learn how to write tabulation in opposite order
Striver, you don't need the DP array of memoization to be of size C, it can be of n size also. It would work absolutely fine.
Such is the beauty of this amazing playlist, our mind is itself writing the code and thinking of the logic of the problem.
But an array of size N will take up more space than an array of size C
try running that in lc and you will get a memory limit exceeded
bro thats because N>C, TRY taking DP SIZE OF 1E5 THEN AND IT WILL ALSO WORK
Was eagerly waiting for this one. Its a very confusing question. Thanks a ton
UNDERSTOOD........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Just in case someone is wondering why sorting, its just to make the formula for length to work otherwise we will not be sure always that arr[j+1] > arr[i-1]. Btw loved the explanationation.
Asusual excellent work striver and thanks a lot for this!! Shouldn't we be starting from j=i to j
Yes, if you start with j = 1 -> n, then there is no need of writing if(i > j) continue; inside the loop.
Understood , thank you so much Raj
i dont know why this golden channel has this few subscribers. I am what else are yu searching for bow down to this king!!!
Superb Explanation!!! espcially the cost logic
Amazing explanation!
Thank You
Understood!!!
Sir Tabulation ma feel nahi aa rahi ha........Bina Memoization ka tabulation nahi likh payaga......
Aur bass Memoziation --> Tabulation convert karta bass baan raha ha....Internally kasia kaam kar raha ha uska koi idea nahi ho raha ha
Even though I still have some points to think carefully, I understood overall idea. Thank you sooooo much as always!
what do you mean by "Even I"
@@jambajuice07 That should be "Even though I", my bad....
Understood, sir. Thank you very much.
I solved this problem without this video but I didn't solved optimally , my soution was of somewhere around 400 ms , after watch I will clear all doubt
understood sir, Thank you very much
Thankyou sir. Understood
As always "understood" ❤️
when we did the recursion, the base case was (i>j) return 0; but incase of tabulation why is j starting from 1 instead of i +1
you can start the j from i. (not i +1 as u mentioned, because when i == j, it does not satisfy base condition)
yes
Thank you
Thanks Striver. Understood
this was awesome great explanation us
isn;t this the vairations of MCM based DP? I found the solution similar to Burst ballons
Best explanation ever
Understood it very nicely, What was in the back though at 11:55 XD
US striver , First difficult one in this playlist
understood as always
Thanks
amazing explanation
nice question
Understood❤❤❤
As always the best One!!
I have doubt I still didn't understand how sorting is relevant [10:45] if 2 is at the end after 5 then won't we take cost 2 because we have [5,2] in the second half of the array. Do you mean cuts here is the cut making on the number line 0 to N thats why we have sorted. For ex: If we making a cut 2 from cuts array are we making a cut on that number line [0 to N] position 2. Am I understanding the question correctly??
Yes, so basically u are making a cut on a stick!
@@takeUforward Thank you so much for making amazing videos with great explanations and clearing my doubt, loving this DP series
understood!!
how to print that order of cutting the sticks so that cost is minimized?
Understood 😊
same question came in codeforces contest currently.
Can anybody please explain why we are sorting the cuts array. I am not getting it.
Why are we using cuts.push_back & cuts.insert?
Understood.
understood ❤
How is this question different from the question min cost to cut the rod in n parys
The time complexity for memoization and tabulation will be o(n^2). Despite, there is a loop inside , we would be calculating the (i,j) subproblem only once.
absolutely
searching for this comment
can someone explain why is there a need to sort the array?
Understood
understood
Understood !
Please tell how did you identify this problem is of MCM and how's this problem different from unbounded knapsack problem of rod cutting
I think if we assume that the costs are based on the index of the cut, then it's a MCM variation whereas If costs array is given for the length of a cut piece, then it becomes a unbounded knapsack problem variation
costs are based on the length to which a cut belongs...so, there are many patterns for re-arranging cuts...Hence, it's a MCM variation
in Tabulation in the 2nd loop why didn't we initialise j from i+1 like we did in mcm ques. ??
the condition i > j will take care
till this video I understood all videos
finally solved at my own ☺☺
In the tabulation code why can't we do for(int j = i + 1; j j) continue;
I tried it but it is giving a wrong answer. Can Someone explain why?
bro u need to start j from i, as i can be equal to j.
in the tabulation code, why are we taking j from 1 to n instead of i+1 to n as j should always be on the right of i like previous mcm problem. pls help
yes you can start j from i to c.......so basically for ( j = i ; j
Can the base case be if (i==j) condition
understood ! awsomme!!
Thanks, mam , eagerly waiting for this, please upload more frequently. ,please.
mam, which mam??
which stuff bro
DP Revision:
This MCM part still feels difficult, had to watch the video to get the logic ;-;
Nov'22, 2023 03:19 pm
(Late due to 2 endsems exam: today morning and yesterday's afternoon.)
striver can you make a summary video of vids of 50-57 to make it more clear
can u show how dp table gets filled
Please make a series on dp on stone games later
In the previous question j was i+1 but here it isn't. Why? In tabulation?
i have the same doubt, do you know the answer now?
Understood 🙂
I dont think I was able to get the approach intuitively, which proves I still have a long way to go.
Yeah, same here
Anyone plzz clear this if we have to choose where we made cuts how we can do and print this is in order ?
@take U forward -> I have still confusion in dp array length , as here also i going from 1 to m then total element is m-1+1=m then why you are taking dp[m+1][m+1] ,why not dp[m][m]
arrays are 0 based indexed always so if we skip 0 index and want 1-based indexing so
we will have to take an array of n+1 size as arr[0] will always exist there we just shifted our
starting index to 1 so ending index should also be shifted by 1 i.e. n+1 and
If 4th index is last index so size will be 5.
@@kapilsingh2816 i is going till n but j is not going till n
Why do we return dp[1][c]?
understood sir🙏🙏❤❤
How the for loop os working i didn't understand that part, even when u reversed i and j value while calculating the cost how is it same as recursion , that cost cal how is it working ???
why the length is cut[j+1] - cut[i-1] and not cut[j+1] - cut[i-1] -1 because I think that gives the actual length between 12 and 3 i.e 8
The length is after the cut is made at length 3 from start so if originally length of stick was 12, then length after the cut should be 9 (12-3)
@@chetanraghavv got it
Understood 🎉
ye kaun hi spch payega lets insert 0 and length of rod in cut arr then for finding the length do that stuff really it is tough
In the first approach u mentioned aux space ...
can u pls tell where is that extra space
It's the stack space for recursion.
Hello Striver base case i>j not cleared😩
basically, if i exceeds j, then there is no partition
Understood !!
Understood Sir!
Striver why you didn't take j from i+1 as in the previous video of MCM tabulation j should be in the right of i?? Please reply 🙏
if you observe the inner loop, the loop just executed the 'continue' statement for all j=i (i.e same as the inner for loop from j=i to c)
Just a doubt instead of taking cuts[j+1]-cuts[i-1] to get the length can we pass the initial length n=7,and for
initial f(i,idx-1,arr[idx]) and f(idx+1,j,n-arr[idx]) ?
1. Try to think why sorting was done.
2. Watch the video from 18:30-19:30 might help.
As per my understanding:
The left subproblem or the left recursion where you are passing arr[idx] will that work ? Or it should be arr[idx]-value at previous_position_where_it_was_cut ? Think on the second or third level of recursion not only on the first level.
I thought the same, but this will increase the space complexity.
Striver's method is better.
see n is bounded by 1e6. so it will give you tle and mle if you take n as a state that is why add n in the array itself and in worst case size of array would be 1e3+1 which will cause no harm.
Just brilliant
UNDERSTOOD
Is the video getting blurred for anyone else ?
Problem link is Not working, Please look into it
You are awesome❤❤
Striver u havent attached the notes for the videos from 40 plz do it helps during revision
Coming soon!
@@takeUforward 🙏
us bhaiyaa after couple of attempts..
plzz reduce your on screen cam size to a square one it's difficult to focus
I have a small doubt, why are you taking the base case of: if(i > j) return 0; and not if(i >= j) return 0; because if i == j, we will have a stick of unit length, and cutting it won't be possible.
Base Case: As i j this is not a valid partition so we can return 0.
if i==j, it doesnt means, we have a stick of unit length, because we are iterating over the cuts[ ] array, so if i==j, means, that we are allowed to cut only at a single place (value of i or j), hence we can use the same formula in this case also for taking out the length of the stick, which is : cuts[j+1]-cuts[i-1]. then the length will be calculated for i==j case
I did n't get sorting part :(
What if 0 and length of stick is already included in cut array, then this solution won't work . We should not insert 0 and length if already exist
see constraints : 1
Sir please make a video on scramble string
Watch it on Aditya Verma playlist. Excellently explained using MCM approach
Understood 😃
Understood :)
Aug'2, 2023 11:10 pm
tell me time complexity of tabulation
Understood!!!!
#include
int f(int start ,int end , vector &cuts , vector &dp) {
if(dp[start][end] != -1)
return dp[start][end];
int value = 1e9 , flag = 0;
for(int i = 0; i < cuts.size(); i++){
if(start < cuts[i] && end > cuts[i]){
flag = 1;
int val = (end - start) + f(start , cuts[i] , cuts , dp) + f(cuts[i] , end , cuts , dp);
value = min(value , val);
}
}
if(flag == 0)
return dp[start][end] = 0;
return dp[start][end] = value;
}
int cost(int n, int c, vector &cuts){
sort(cuts.begin() , cuts.end()) ;
vector dp(n+1 , vector (n+1 , -1));
return f( 0 , n , cuts , dp);
}
I SOLVE USING THIS CODE ITS BIT DIFFERENT IT GOT accepted on coding ninjas but its giving memory limit exceeded error on leetcode can anyone tell me whst is the reason ?
I am glad you said it a hard problem! LOL
US