We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Cut a Stick

Number: 1669

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Apple, PhonePe

Problem Description

Given a stick of length n with positions marked for cuts, determine the minimum total cost to cut the stick. You are allowed to perform the cuts in any order, and each cut's cost is equal to the length of the stick segment being cut at that time. The goal is to choose an order of cuts that minimizes the overall cost.

Key Insights

  • Sort the list of cuts and include the two boundaries (0 and n) to enable easier segment computation.
  • Use dynamic programming where dp[i][j] represents the minimum cost to cut the stick between positions[i] and positions[j].
  • The cost to perform a cut is the length of the current segment (positions[j] - positions[i]).
  • For each segment, try each cut between the boundaries to determine the optimal cost using the recurrence:
      dp[i][j] = min(dp[i][k] + dp[k][j] + (positions[j] - positions[i])) for every k such that i < k < j.
  • The problem exhibits optimal substructure, making it suitable for a bottom-up DP approach.

Space and Time Complexity

Time Complexity: O(m^3), where m is the number of cut positions plus two (boundaries). Given that m is at most 102, this cubic time is acceptable. Space Complexity: O(m^2) to store the dynamic programming table.

Solution

We approach this problem using a bottom-up dynamic programming algorithm. First, sort the cuts array and add the boundaries 0 and n. This results in an array positions where positions[0] = 0 and positions[m-1] = n. Then, define dp[i][j] as the minimum cost to cut the segment from positions[i] to positions[j]. For each interval, try every possible intermediate cut position k (where i < k < j) to determine the cost of cutting that segment. The recurrence relation is:

  dp[i][j] = min(dp[i][k] + dp[k][j] + (positions[j] - positions[i])), for every valid k

Initialize dp[i][j] = 0 for segments that have no cuts between them (i.e. j = i+1). Build the solution from smaller segments up to the entire stick. Finally, the answer is dp[0][m-1].

Code Solutions

# Python solution for Minimum Cost to Cut a Stick

def minCost(n, cuts):
    # Sort the cuts and add boundaries 0 and n.
    positions = [0] + sorted(cuts) + [n]
    m = len(positions)
    
    # Initialize dp table with 0's.
    dp = [[0] * m for _ in range(m)]
    
    # Build the dp table from smaller segments (gap) to larger ones.
    for gap in range(2, m):  # gap is the window size between i and j.
        for i in range(m - gap):
            j = i + gap
            min_cost = float('inf')
            # Try every possible cut between positions[i] and positions[j]
            for k in range(i + 1, j):
                cost = dp[i][k] + dp[k][j] + positions[j] - positions[i]
                min_cost = min(min_cost, cost)
            dp[i][j] = min_cost
    return dp[0][m - 1]

# Example usage:
print(minCost(7, [1, 3, 4, 5]))  # Output: 16
← Back to All Questions