DP 50. Minimum Cost to Cut the Stick

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

[@sarthakchauhan8386]

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.

[@champion5946]

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 😂

[@adityasaxena6971]

same situation😂

[@pqrstwxyz1175]

Whats the situation of you guys now ?

[@iamnoob7593]

@@pqrstwxyz1175 hows urs?

[@shinewanna3959]

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

[@priyanshkumariitd]

Yes, I also observed this

[@atifmirza9168]

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

[@girishbhargava6367]

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.

[@parthsalat]

But an array of size N will take up more space than an array of size C

[@mayanksharma2039]

try running that in lc and you will get a memory limit exceeded

[@07rockzz92]

bro thats because N>C, TRY taking DP SIZE OF 1E5 THEN AND IT WILL ALSO WORK

[@adityagoel7376]

i dont know why this golden channel has this few subscribers. I am what else are yu searching for bow down to this king!!!

[@neelabhabanerjee8247]

Was eagerly waiting for this one. Its a very confusing question. Thanks a ton

[@stith_pragya]

UNDERSTOOD........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@satyampriyadarshi6455]

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.

[@aadishjain473]

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

[@DevashishJose]

Understood , thank you so much Raj

[@ishangujarathi10]

Superb Explanation!!! espcially the cost logic

[@cinime]

Even though I still have some points to think carefully, I understood overall idea. Thank you sooooo much as always!

[@jambajuice07]

what do you mean by "Even I"

[@cinime]

@@jambajuice07 That should be "Even though I", my bad....

[@suchithreddy733]

Asusual excellent work striver and thanks a lot for this!! Shouldn't we be starting from j=i to j

[@priyanshkumariitd]

Yes, if you start with j = 1 -> n, then there is no need of writing if(i > j) continue; inside the loop.

[@UECAshutoshKumar]

Thank You Understood!!!

[@bhaskarmishra8479]

Amazing explanation!

[@xolo2617]

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

[@preetisahani5054]

Understood it very nicely, What was in the back though at 11:55 XD

[@JitendraKumar-ti6yd]

isn;t this the vairations of MCM based DP? I found the solution similar to Burst ballons

[@Hrushi_2000]

Thankyou sir. Understood

[@1tav0]

this was awesome great explanation us

[@gauravmehta4011]

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

[@sourabhsejwal4079]

you can start the j from i. (not i +1 as u mentioned, because when i == j, it does not satisfy base condition)

[@ujjalsaha428]

As always "understood" ❤️

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@rishabhagarwal8049]

understood sir, Thank you very much

[@vinayverma8897]

how to print that order of cutting the sticks so that cost is minimized?

[@sameersahu4569]

Thank you

[@neelabhabanerjee8247]

Best explanation ever

[@ganeshkamath89]

Thanks Striver. Understood

[@iamnoob7593]

US striver , First difficult one in this playlist

[@wigglesort]

Can anybody please explain why we are sorting the cuts array. I am not getting it.

[@prabhakaran5542]

Understood❤❤❤

[@techdemy4050]

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

[@takeUforward]

Yes, so basically u are making a cut on a stick!

[@techdemy4050]

@@takeUforward Thank you so much for making amazing videos with great explanations and clearing my doubt, loving this DP series

[@Aditya-rs5dj]

amazing explanation

[@divyachopra2369]

How is this question different from the question min cost to cut the rod in n parys

[@adarshmishra7113]

understood as always

[@akashsahu2571]

yes

[@jyothiyadav2595]

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

[@aryansinha1818]

Why are we using cuts.push_back & cuts.insert?

[@pratyushgupta5487]

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?

[@vanshsehgal9475]

bro u need to start j from i, as i can be equal to j.

[@satyampande684]

understood!!

[@sahild5953]

can someone explain why is there a need to sort the array?

[@cristeinfuze8574]

Anyone plzz clear this if we have to choose where we made cuts how we can do and print this is in order ?

[@ashvinkumhar5819]

As always the best One!!

[@parthstark2934]

nice question

[@edgyboi69]

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

[@altamashsabri8142]

yes you can start j from i to c.......so basically for ( j = i ; j

[@dheerajbhardwaj6086]

Thanks

[@arihantjammar8888]

Understood 😊

[@girikgarg8]

Can the base case be if (i==j) condition

[@LBK3]

understood ❤

[@rahatsshowcase8614]

understood ! awsomme!!

[@sparks8754]

in Tabulation in the 2nd loop why didn't we initialise j from i+1 like we did in mcm ques. ??

[@gv_1010]

the condition i > j will take care

[@tikshavarshney213]

Understood !

[@anshumangupta1001]

Understood.

[@Skm-mq1sw]

Understood

[@nickatytepro8690]

striver can you make a summary video of vids of 50-57 to make it more clear

[@bahveshjain1730]

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 🙏

[@kiransequeira6152]

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)

[@coding8000]

Thanks, mam , eagerly waiting for this, please upload more frequently. ,please.

[@menhihubhai]

mam, which mam??

[@vaibhavsaharan7898]

which stuff bro

[@awggeez]

Why do we return dp[1][c]?

[@abhisheksingharya651]

understood

[@alfredeinstein1742]

Please tell how did you identify this problem is of MCM and how's this problem different from unbounded knapsack problem of rod cutting

[@vaibhavsaharan7898]

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

[@priyanshkumariitd]

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

[@kongzilla2897]

Problem link is Not working, Please look into it

[@pulkitranjan8189]

till this video I understood all videos

[@anirbanpaul5687]

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

[@hrithiksomani]

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.

[@aryanyadav3926]

I thought the same, but this will increase the space complexity. Striver's method is better.

[@soumyajitmishra6855]

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.

[@yeswanthh5068]

Understood 🙂

[@Nitro-kx7ok]

understood sir🙏🙏❤❤

[@amitranjan6998]

@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]

[@kapilsingh2816]

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.

[@pranavsharma7479]

@@kapilsingh2816 i is going till n but j is not going till n

[@googleit2490]

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.)

[@its_me136]

finally solved at my own ☺☺

[@_inspireverse___]

You are awesome❤❤

[@dss963]

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.

[@user-ul9fq3xt9c]

absolutely searching for this comment

[@dhanashreegodase4445]

can u show how dp table gets filled

[@yashmamidwar6729]

Understood !!

[@vinayyelleti2714]

In the first approach u mentioned aux space ... can u pls tell where is that extra space

[@rajalakshmis7308]

It's the stack space for recursion.

[@abhilashghosh4014]

Please make a series on dp on stone games later

[@GeniuslyTensai]

In the previous question j was i+1 but here it isn't. Why? In tabulation?

[@sahilsaini4574]

i have the same doubt, do you know the answer now?

[@Raj10185]

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

[@OtakuRiku]

I think the link to the notes isnt redirecting to the desired page. Can u look into it? Thanks!

[@original_gangsta_]

UNDERSTOOD

[@anthonyjaurique1979]

Is the video getting blurred for anyone else ?

[@vaishnavithakur6460]

Understood!!!!

[@VikashYadav-px8ei]

Understood 🎉

[@apurbanath4822]

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.

[@kartikeyjangir6003]

Base Case: As i j this is not a valid partition so we can return 0.

[@ritvikverma1443]

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

[@saunaknandi1814]

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

[@chetanraghavv]

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)

[@saunaknandi1814]

@@chetanraghavv got it

[@shikharbansal2942]

Just brilliant

[@parshchoradia9909]

Understood Sir!

[@jm_ohit]

same question came in codeforces contest currently.

[@souvickmazumdar8129]

Understood 😃

[@amancuber5235]

I am glad you said it a hard problem! LOL

[@amansamal8233]

understood😍

[@sauravchandra10]

I dont think I was able to get the approach intuitively, which proves I still have a long way to go.

[@priyanshkumariitd]

Yeah, same here

[@aakashgoswami2356]

I did n't get sorting part :(

[@Anschlusss]

Understood!!! ❤❤❤

[@mohitsinghnegi9677]

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

[@priyanshkumariitd]

see constraints : 1

[@SajanKumar-ec2us]

tell me time complexity of tabulation

[@naman_goyal]

Amazing

[@rahil_rehan]

How is this problem different from rod cutting or unbounded knapsack problem?

[@rajeshg8649]

In rod cutting problem, we can try out all the possible cuts. But in this problem, we have to do the cut at the given indices only and we should explore all the different possible cuts.

[@tusharbhatia9930]

Cant we just solve the problem in a different way like we create a look for a lower bound of (j+i)/2 on cuts vector ad cut the stick from there on the current rod. Is this approach correct.for eg- in the testcase we have n = 7, cuts = [1,3,4,5] and the correct pattern of cuts is [3, 5, 1, 4] to get the minimum cost so can we think in a way that 3 is the lowerbound of (0+7)/2 and so we cut from 3 next we have two rods 1-we solve for first half from [0,3] for this the lower bound of (0+3)/2 in the vector is 1 so next cut from 1 2-we solve for other half that is [3,7] the lower bound of (3+7)/2 will be 5 so now the cut will be from 5 . IS this approach wrong?

[@anshumansharma4580]

How is the lower bound coming? Like your approach seems intersting, can you code it once?

[@deepakagrawal7687]

problems seems to be same as rod cutting problem of subsequence section. how to identify whether it falls under partition problem of subsequence? @Striver

[@akshayverma4540]

I also have the same query

[@ec-223ujjawalkumar5]

plzz reduce your on screen cam size to a square one it's difficult to focus