Minimum Cost to Cut a Stick - Leetcode 1547 - Python

[@NeetCodeIO]

Correction, time complexity should be O(M^3), no need to include N, since we wont necessarily cut it at every point.

[@chaithanyachallapalli8608]

could u explain to get order in which we need to cut the rod

[@maotay]

Hi, Can you solve this problem by using dynamic programing?

[@abhimanyuraizada7713]

@@maotay yes, in the solution it dp only

[@yashmundada2483]

I think this it would be really important to explain that instead of a map if you use an array to store the values, you'll get MLE.. Using a map works here since most values actually aren't required since you're skipping them. Same is the idea with the time complexity !

[@jlecampana]

Hey Neet thank you so much for this one, Leetcode should hire you to make their video solution editorials! You're the Best, kind sir!

[@ExylonBotOfficial]

Would it be possible to optimize it by trying to cut a stick in the point that is closer to the middle? Or if there are two points with equal distance from the middle, then try both and return the lowest cost

[@AlexNikiporenko]

First, thank you for your regular videos and clear explanations, Neetcode! In my solution, I sorted the array first, and also added 0 and n values to the array. I think it is a simpler approach: def minCost(n: int, cuts: list[int]) -> int: cuts = [0] + sorted(cuts) + [n] cache = {} def recursive(l, r): if r - l == 1: return 0 if (l,r) in cache: return cache[(l,r)] cache[(l,r)] = cuts[r] - cuts[l] + min([recursive(l, m) + recursive(m, r) for m in range(l+1, r)]) return cache[(l,r)] return recursive(0, len(cuts)-1)

[@avikmallick2493]

According to the constraints this problem needs to be solved in another approach where the recurrence relation depends on the cuts array not the len of the stick

[@ningzedai9052]

The top-down solution doesn't deserve the "Hard" label, the real hard part of this problem is to come up the bottom-up solution.

[@akshatsingh5475]

Thank you

[@shivkrishnajaiswal8394]

@NeetcodeIO Nice Solution. You can get rid of inf. So if a stick can not be cut, cost will be 0. Below is the code. from functools import cache class Solution: def minCost(self, n: int, cuts: list[int]) -> int: @cache def dfs(l: int, r: int) -> int: w = r - l return min( (w + dfs(l, c) + dfs(c, r) for c in cuts if l < c < r), default=0 ) return dfs(0, n)

[@maotay]

Hi, Can you solve this problem by using dynamic programing?

[@yeah5037]

Thanks man , u are the GOAT

[@AmaanKhan-vc9tb]

Honestly I don’t feel the question was worded wrong, although a bit tricky. You must cut it in an order just means you cannot cut simultaneously, and not necessarily in the given order.

[@ГорячийМексиканец-ч9в]

Just to be precise, for this specific task, the overall complexity can be improved from O(N^3) to O(N^2) via the Knuth's Optimization, possible because of the cost function properties.

[@lucas29476]

Indeed! Knuth's Optimisation is perfect for such cases when the cost function is a subarray sum.

[@karthick5032]

can you explain why a greedy solution wont work in this case

[@sanjeevrajora7335]

thanks for this explanatory video

[@anupamkolay193]

Thank you so much for these daily challenge questions. Your explanations are just so easy to understand. Love from India.

[@dashdoom8452]

Sometimes with problems like this I have trouble figuring out what parameters to cache the results by. Any tips on figuring out what we need to cache the results by in any problem?

[@shashanksingh4708]

Even I struggle with the same . You can try writing the recursive solution first, then maybe drawing its recursive tree . Sometimes this helps me identify what are the subproblems being repeated, and what to cache.

[@kshitijgarg2609]

wonderful explanation

[@nizarkadri3109]

I didn't understand why we are adding these (r - l) + dfs(l, c) + dfs(c, r) , isn't r-l the length of rod? and why do we need to add both left and right cuts

[@ExylonBotOfficial]

The cost for cutting a stick is the length of the stick you cut, plus the costs of cutting the two sticks that your are left with after cutting the first one.

[@uptwist2260]

Thanks for the daily

[@Cheng-K]

Thank you!

[@acceleratorlevel645]

Lmao man, i guess i have gotten better cuz this is the solution i kind of thought but just wasnt sure about it in few parts, so checked to see if i was correct 😅.

[@krateskim4169]

Thanks

[@siddheshb.kukade4685]

thanks neet

[@chaithanyachallapalli8608]

can anyone explain how to get the order in which we need to cut the rod

[@NirmalSilwal]

java implementation - class Solution { Map cacheMap = new HashMap(); public int minCost(int n, int[] cuts) { return dfs(0, n, cuts); } private int dfs(int left, int right, int cuts[]) { if (right - left == 1) return 0; String currentPair = left + "," + right; if (cacheMap.containsKey(currentPair)) { return cacheMap.get(currentPair); } int result = Integer.MAX_VALUE; for (int c : cuts) { if (left < c && c < right) { int currResult = (right - left) + dfs(left, c, cuts) + dfs(c, right, cuts); result = Math.min(result, currResult); } } result = (result == Integer.MAX_VALUE) ? 0 : result; cacheMap.put(currentPair, result); return result; } }

[@alek4001]

Interestingly enough, but if we use 2d array for memo we get Memory limit exceeded. public class Solution { public int minCost(int n, int[] cuts) { int[][] memo = new int[n + 1][n + 1]; return dfs(cuts, 0, n, memo); } private int dfs( int[] cuts, int left, int right, int[][] memo) { if(left - right == 1) return 0; if(memo[left][right] != 0){ return memo[left][right]; } int result = Integer.MAX_VALUE; for (int i = 0; i < cuts.length; i++) { if(cuts[i] < right && cuts[i] > left) { result = Math.min(result, right - left + dfs(cuts, left, cuts[i], memo) + dfs(cuts, cuts[i], right, memo)); } } if(result == Integer.MAX_VALUE) result = 0; memo[left][right] = result; return result; } }

[@alek4001]

I'm just wondering. Wont we get the same issue if we solve it bottom up using tabulation like the Tip suggests

[@vijayj1997]

hi neetcode while you are trying to solve this, did you come up with your own solution ? bcoz i solved nearly 400+ problems i didn’t able to come up with this solution am i really bad ? or the problem ?

[@yolo3659]

Yeah yeah it happens.. I have solved around 550 questions but still end up confused and blank with some questions. Just never stop learning new methods and see where you are lacking and solve more questions on those topics.. For me it is graphs... :)

[@MohamedIbrahim-yg7of]

@@yolo3659 can we make group and solve with each other !

[@kirillzlobin7135]

Amazing

[@c0dertang]

"someone should put down the crack pipe" - neetcode 2023 Jokes aside, I was wondering why the official solution sorts the array before solving

[@NeetCodeIO]

They use a pretty clever variation of the solution I presented, where instead of needing an 'if-statement' to check if a cut applies to the current stick, we can just pass the appropriate subarray of cuts into the recursive call. In that solution left and right refer to the index of `cuts`, rather than the edges of the current stick.

[@julianelmasry9556]

can anyone explain the time complexity here?

[@adwaitarajmodak213]

class Solution { public: int dfs(int l, int r , vector &cuts,vector&dp){ if(r-l==1)return 0; if(dp[l][r]!=-1){ return dp[l][r]; } int res=INT_MAX; for(auto c:cuts){ if(c>l && c

[@prakashmohaldar9004]

bro did you got the problem ?

[@priyank1873]

I got the same , Memory limit exceeded issue, then i tried hashmap, instead of vector of vector... class Solution { public: int util(int i, int j, vector& cuts, unordered_map& dp) { if (i + 1 == j) { return 0; } string key = to_string(i) + "_" + to_string(j); if (dp.count(key) != 0) { return dp[key]; } int res = INT_MAX; for (int x = 0; x < cuts.size(); x++) { if (cuts[x] > i && cuts[x] < j) { int cost = j - i; cost += util(i, cuts[x], cuts, dp); cost += util(cuts[x], j, cuts, dp); res = min(res, cost); } } if (res == INT_MAX) { res = 0; } dp[key] = res; return res; } int minCost(int n, vector& cuts) { unordered_map dp; return util(0, n, cuts, dp); } }; This code gave TLE, even though all test case passed. Leetcode just doesnt want this solution in c++

[@rowanus116]

Don't use vector, use unordered_map or map instead. Reason is: vector has pre-allocated space(even some cache might miss), whereas hashmap or map only uses necessary(cache hit) memory. You can try to verify the result by checking the vector how much cache has been missed (value, -1). But the downside is you'll have to provide your own hashfuc if you go with unordered_map(collision, might hurt the runtime complexity). Hope that helps.

[@jessanraj9086]

Thank you so much

[@YouTube_Staff]

Whoever is coming up with these descriptions needs to chill out with the loopy loop. Reminds me of the meme "Every 60 seconds in Africa a minute passes".

[@6kostia]

Same solution but 1 second faster: class Solution: def minCost(self, n: int, cuts: List[int]) -> int: cuts.sort() @lru_cache(None) def dfs(l: int, r: int) -> int: if l >= r - 1: return 0 res = float("inf") for i in range(bisect_left(cuts, l), bisect_right(cuts, r)): if l < cuts[i] < r: res = min(res, dfs(l, cuts[i]) + dfs(cuts[i], r) + r - l) return res if res != float("inf") else 0 return dfs(0, n)

[@MP-ny3ep]

Thank you !