⚡Flashcard Drill➔
NeetCode #749LC-1547Hard2-D Dynamic Programming
← Back to All Problems

#749 · #1547 · Minimum Cost to Cut a Stick(切棍子的最小成本)

📌 Problem Statement & Constraints

A wooden stick of length n has cut positions cuts. Each cut costs the length of the stick being cut at that moment. Return the minimum total cost to perform every cut. Constraints: 2 <= n <= 10^6, 1 <= cuts.length <= 100, 1 <= cuts[i] <= n - 1, and all cuts[i] are distinct.

💡 Core Algorithmic Approaches

  1. Add the endpoints 0 and n to the cut list and sort it; the segments between consecutive boundaries are the subproblems.
  2. Let dp[i][j] be the minimum cost to perform every cut strictly between boundaries cuts[i] and cuts[j].
  3. The first cut inside the segment can be any k with i < k < j; it costs cuts[j] - cuts[i] and splits the problem into dp[i][k] and dp[k][j].
  4. So dp[i][j] = cuts[j] - cuts[i] + min over k of (dp[i][k] + dp[k][j]), filled by increasing segment width.

💻 Benchmark Python3 Implementation

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts = sorted(cuts + [0, n])
        m = len(cuts)
        # dp[i][j] = min cost to make every cut strictly between cuts[i] and cuts[j]
        dp = [[0] * m for _ in range(m)]
        for span in range(2, m):              # number of gaps in the segment
            for i in range(m - span):
                j = i + span
                best = float("inf")
                for k in range(i + 1, j):
                    best = min(best, dp[i][k] + dp[k][j])
                dp[i][j] = best + cuts[j] - cuts[i]
        return dp[0][m - 1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m^3) where m = cuts.length + 2: O(m^2) intervals each trying O(m) split points.
💾 Space Complexity
O(m^2): the interval table.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the endpoints 0 and n: without them the first and last segments cannot be represented, and the cost formula has no anchor.
  • Not sorting the cuts: the interval DP assumes ordered boundaries.
  • Adding the segment length inside the min: the current cut's cost cuts[j] - cuts[i] is paid once per interval, not per split point.
  • Fixing the cut order: the optimal order is exactly what is being optimised, so all split points must be tried.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems