Minimum Cost to Cut a Stick - Leetcode 1547 - Python

Solving leetcode 1547 - Minimum Cost to Cut a Stick, today's daily leetcode problem on may 27.

0:00 - Read the problem
0:46 - Drawing Explanation
8:15 - Coding Explanation

leetcode 1547

#neetcode #leetcode #python

[NeetCodeIO]

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

[yashmundada]

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!

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

[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

[ningzedai]

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.

[avikmallick]

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

[pbergn]

It should have been, "You should perform the cuts sequentially, and you can change the order of the cuts as you wish."

[shivkrishnajaiswal]

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

[karthick]

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

[chaithanyachallapalli]

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

[nizarkadri]

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

[dashdoom]

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?

[anupamkolay]

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

[AmaanKhan-vctb]

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.

[acceleratorlevel]

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

[vijayj]

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 ?

[NirmalSilwal]

java implementation -

class Solution {

Map<String, Integer> 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 {
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;
}
}

[julianelmasry]

can anyone explain the time complexity here?