Minimum Cost to Cut a Stick - Practice Coding Problems

Minimum Cost to Cut a Stick - Problem

Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

[0] --- [1] --- [2] --- [3] --- [4] --- [5] --- [6]

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut).

Return the minimum total cost of the cuts.

Input & Output

Example 1 — Basic Case

$ Input: n = 7, cuts = [1,3,4,5]

› Output: 16

💡 Note: One optimal order: cut at 5 (cost=7), then cut at 3 (cost=5), then cut at 4 (cost=2), then cut at 1 (cost=3). Total: 7+5+2+3=17. Better order exists with cost 16.

Example 2 — Single Cut

$ Input: n = 9, cuts = [5]

› Output: 9

💡 Note: Only one cut at position 5, so the cost is the length of the entire stick: 9.

Example 3 — Two Cuts

$ Input: n = 6, cuts = [2,4]

› Output: 8

💡 Note: Cut at 2 first (cost=6), then cut at 4 in right piece (cost=4-2=2). Total: 6+2=8. Or cut at 4 first (cost=6), then at 2 in left piece (cost=4-0=4). Total: 6+4=10. Minimum is 8.

Constraints

2 ≤ n ≤ 10⁶
1 ≤ cuts.length ≤ min(n - 1, 100)
1 ≤ cuts[i] ≤ n - 1
All the integers in cuts array are distinct.

Visualization

Tap to expand

Understanding the Visualization

Input

Stick of length 7 with cuts at [1,3,4,5]

Process

Find optimal order of cuts to minimize total cost

Output

Minimum total cost is 16

Key Takeaway

🎯 Key Insight: The order of cuts matters - cutting creates smaller pieces which reduces future cutting costs

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that this is an interval DP problem where the cost depends on the current stick length. The optimal approach uses bottom-up dynamic programming with sorted cuts and boundary conditions. Time: O(m³), Space: O(m²).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(m³)	O(m²)	Cache results of overlapping subproblems to avoid recomputation
Recursive with All Orders	O(m! × m²)	O(m)	Try all possible orders of cuts recursively
Bottom-up Dynamic Programming	O(m³)	O(m²)	Build solution iteratively using 2D DP table

Memoized Recursion — Algorithm Steps

Sort cuts and add boundaries 0 and n
Use memoization with interval indices
For each interval, try all possible cuts
Cache and return minimum cost

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Add Boundaries

Create sorted array [0, cuts..., n]

Memoize Intervals

Cache results for each interval [i,j]

Optimal Substructure

Build solution from cached subproblems

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int memo[102][102];
int sortedCuts[102];
int cutsSize;

int dp(int i, int j) {
    if (i + 1 >= j) return 0;
    
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    
    int result = INT_MAX;
    for (int k = i + 1; k < j; k++) {
        int cost = sortedCuts[j] - sortedCuts[i];
        int leftCost = dp(i, k);
        int rightCost = dp(k, j);
        int total = cost + leftCost + rightCost;
        if (total < result) {
            result = total;
        }
    }
    
    memo[i][j] = result;
    return result;
}

int cmp(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int n, int* cuts, int cuts_size) {
    // Add boundaries and sort
    sortedCuts[0] = 0;
    for (int i = 0; i < cuts_size; i++) {
        sortedCuts[i + 1] = cuts[i];
    }
    sortedCuts[cuts_size + 1] = n;
    cutsSize = cuts_size + 2;
    
    qsort(sortedCuts, cutsSize, sizeof(int), cmp);
    
    // Initialize memo
    for (int i = 0; i < 102; i++) {
        for (int j = 0; j < 102; j++) {
            memo[i][j] = -1;
        }
    }
    
    return dp(0, cutsSize - 1);
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int cuts[100];
    int cuts_size = 0;
    
    char* token = strtok(line, "[],");
    while (token != NULL) {
        cuts[cuts_size++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    
    int result = solution(n, cuts, cuts_size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m³)

m² subproblems, each taking O(m) time to solve

✓ Linear Growth

Space Complexity

O(m²)

Memoization table stores results for all interval pairs

✓ Linear Space

125.0K Views

Medium Frequency

~35 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler