Cheapest Stick Cuts
Problem
A wooden stick of a given length must be cut at every position in a list of marks, each strictly between 0 and length and all different. A saw charges the current length of the piece it cuts, so the order of the cuts changes the bill. Return the smallest total charge for making all the cuts. With no marks there is nothing to pay.
Examples
Input: length = 10, marks = [2, 4, 7]
Output: 20
Why: cut at 4 (pays 10), then at 2 (pays 4), then at 7 (pays 6)Input: length = 9, marks = [5, 1, 6, 3]
Output: 21
Why: marks can arrive in any order; only their positions matterInput: length = 6, marks = []
Output: 0
Why: edge case, no cutsHints
0 / 3
Choosing the first cut greedily, say the one nearest the middle, is not always best. Something has to compare every possible order without listing all of them.
Once a cut is made, the two pieces never influence each other again. Which cut is made first inside a piece decides how that piece splits.
Sort the marks and add 0 and length as fixed ends. For every pair of ends i and j, the cheapest cost is the piece length plus the best split over each mark k strictly between them of cost(i, k) + cost(k, j). Fill pairs from the closest ends outward.
Solution
After the first cut inside a piece, the left and right parts are cut independently, so the cheapest cost of a piece is its length plus the best over every first cut of the two parts' costs. With the marks sorted and 0 and length added as ends, every piece is a stretch between two of these points, which is interval dynamic programming. Stretches with no mark inside cost nothing, and filling by increasing width guarantees the smaller stretches are ready. Time is O(m cubed) and space is O(m squared) for m marks.
def min_cut_cost(length, marks):
ends = [0] + sorted(marks) + [length]
m = len(ends)
best = [[0] * m for _ in range(m)] # best[i][j] = cheapest cuts strictly inside ends i..j
for width in range(2, m): # stretches that hold at least one mark
for i in range(m - width):
j = i + width
first = min(best[i][k] + best[k][j] for k in range(i + 1, j))
best[i][j] = ends[j] - ends[i] + first # the first cut pays the whole stretch
return best[0][m - 1]
print(min_cut_cost(10, [2, 4, 7])) # -> 20
print(min_cut_cost(9, [5, 1, 6, 3])) # -> 21
print(min_cut_cost(6, [])) # -> 0Stuck on the idea rather than the code? Interval DP covers it.