Dynamic Programming • Interval DP

Minimum Cost to Cut a Stick

Given a stick of length n and an array of cuts, find the minimum cost to perform all cuts where the cost of a cut is the length of the current stick.

Try Interactive Simulator

Overview

This is a classic Interval DP problem. Just like Matrix Chain Multiplication, the cost depends on which cut you make first (i.e. where you split the interval).

Array Transformation

To easily calculate stick lengths, we add the boundaries `0` and `n` to the cuts array and sort it. Now, cuts become interval boundaries.

The Cost Function

If we cut interval `[i, j]` at point `k`, the cost is the cost to cut the left piece `[i, k]` plus the right piece `[k, j]`, plus the length of the current stick `cuts[j] - cuts[i]`.

Length Iteration

We process intervals by length, starting from length 2 (which means 1 cut in between). A length of 1 means no cuts are between `i` and `j`, so the cost is 0.

0

1

3

4

7

I=0	0	0	0	0
I=1	0	0	0	0
I=2	0	0	0	0
I=3	0	0	0	0

Code Tracker

:::

1cuts.push(0, n);

2cuts.sort((a, b) => a - b);

3let m = cuts.length;

4let dp = Array.from({ length: m }, () => Array(m).fill(0));

5for (let len = 2; len < m; len++) {

6 for (let i = 0; i < m - len; i++) {

7 let j = i + len;

8 dp[i][j] = Infinity;

9 for (let k = i + 1; k < j; k++) {

10 let cost = dp[i][k] + dp[k][j] + (cuts[j] - cuts[i]);

11 dp[i][j] = Math.min(dp[i][j], cost);

12 }

13 }

14}

15return dp[0][m-1];

Min Cost Cut Stick

Min Cost Cut Stick

Minimum Cost to Cut a Stick

Overview

Array Transformation

The Cost Function

Length Iteration

Minimum Cost to Cut a Stick

Overview

Array Transformation

The Cost Function

Length Iteration