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 !
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)
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
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
@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)
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.
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.
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 😅.
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?
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.
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
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.
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; } }
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; } }
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.
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)
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
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++
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.
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 ?
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... :)
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".
