Leetcode 1547. Minimum Cost to Cut a Stick
Problem Explanation
We are given a wooden stick of length n
and a list named cuts
containing the positions where we need to cut the stick. We have to perform the cuts in such a way that it minimizes the total cost. The cost for each cut is the length of the stick being cut. We can rearrange the order of the cuts to minimize the total cost.
Let's take an example for better understanding. Suppose the length of the stick n
is 7 and cuts
is [3,5,1,4].
1 2 3Stick: --------- (7 units) 4Cuts: 3, 5, 1, 4
If we perform the cuts in the same order, the cost would be 7 + 4 + 3 + 2 = 16. So, the we rearrange the cuts
in order to minimize the cost.
Approach
To solve this problem, we'll use a variation of matrix chain multiplication, a dynamic programming algorithm, that allows us to evaluate sequences in order to get the optimal solution.
We initialize the cuts
array by adding two endpoints (0 and n). This is because the first and last points on the stick are always going to be cut locations. We then sort the cuts, and prepare a DP table. dp[i][j]
represents the minimum cost to cut the stick from cuts[i]
to cuts[j]
. The DP equation here is:
1 2 3dp[i][j] = min(dp[i][j], cuts[j] - cuts[i] + minCost(cuts, i, k) + minCost(cuts, k, j))
Here k
is the index of an intermediate cut between i
and j
. The minCost
function calculates the minimum cost to cut the stick from cuts[i] to cuts[j].
Let's see how this works using Python code.
Python
1 2python 3class Solution: 4 def minCost(self, n, cuts): 5 # Adding the two endpoints 6 cuts.append(0) 7 cuts.append(n) 8 # Sorting the 'cuts' 9 cuts.sort() 10 # Initializing the DP table 11 dp = [[0 for _ in range(len(cuts))] for _ in range(len(cuts))] 12 13 for l in range(2, len(cuts)): 14 for i in range(len(cuts) - l): 15 j = i + l 16 dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i+1, j)) + cuts[j] - cuts[i] 17 18 return dp[0][-1]
Java
1 2java 3public class Solution { 4 public int minCost(int n, int[] cuts) { 5 int m = cuts.length; 6 int[] c = Arrays.copyOf(cuts, m + 2); 7 c[m] = 0; 8 c[m + 1] = n; 9 Arrays.sort(c); 10 11 int[][] dp = new int[m + 2][m + 2]; 12 for (int d = 2; d < m + 2; ++d) 13 for (int i = 0; i < m + 2 - d; ++i) { 14 int j = i + d; 15 dp[i][j] = Integer.MAX_VALUE; 16 for (int k = i + 1; k < j; ++k) 17 dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + c[j] - c[i]); 18 } 19 20 return dp[0][m + 1]; 21 } 22}
JavaScript
1 2javascript 3var minCost = function(n, cuts) { 4 cuts.push(0, n); 5 cuts.sort((a, b) => a - b); 6 const dp = Array.from({ length: cuts.length }, () => new Array(cuts.length).fill(0)); 7 8 for (let i = cuts.length - 2; i >= 0; i--) { 9 for (let j = i + 2; j < cuts.length; j++) { 10 dp[i][j] = Number.MAX_SAFE_INTEGER; 11 for (let k = i + 1; k < j; k++) { 12 dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]); 13 } 14 dp[i][j] += cuts[j] - cuts[i]; 15 } 16 } 17 return dp[0][cuts.length-1]; 18};
C++
1 2cpp 3class Solution { 4public: 5 int minCost(int n, vector<int>& cuts) { 6 cuts.push_back(0); 7 cuts.push_back(n); 8 sort(cuts.begin(), cuts.end()); 9 int dp[102][102] = {0}; 10 11 for (int i = cuts.size()-3; i >= 0; --i) { 12 for (int j = i+2; j < cuts.size(); ++j) { 13 dp[i][j] = INT_MAX; 14 for (int k = i+1; k < j; ++k) 15 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]); 16 } 17 } 18 19 return dp[0][cuts.size()-1]; 20 } 21};
C#
1 2csharp 3public class Solution { 4 public int MinCost(int n, int[] cuts) { 5 Array.Sort(cuts); 6 int[] new_cuts = new int[cuts.Length + 2]; 7 Array.Copy(cuts, 0, new_cuts, 1, cuts.Length); 8 new_cuts[new_cuts.Length - 1] = n; 9 cuts = new_cuts; 10 int[,] dp = new int[cuts.Length, cuts.Length]; 11 for (int i = cuts.Length - 2; i >= 0; i--) { 12 for (int j = i + 2; j < cuts.Length; j++) { 13 dp[i,j] = int.MaxValue; 14 for (int k = i + 1; k < j; k++) { 15 dp[i,j] = Math.Min(dp[i,j], dp[i,k] + dp[k,j]); 16 } 17 dp[i,j] += cuts[j] - cuts[i]; 18 } 19 } 20 return dp[0, cuts.Length - 1]; 21 } 22}
This problem has an optimal substructure, meaning the optimal solution can be constructed from the optimal solutions of its subproblems, and has overlapping subproblems, meaning a recursive solution contains a small number of distinct subproblems repeated many times.
The dynamic programming solution ensures efficiency by storing the results of intermediate computations in the DP table and reusing them, thus avoiding redundant calculations that would occur with a naive recursive approach. This makes the solution more performant for larger inputs.
To conclude, if you encounter a similar problem where the order of operations affects the outcome and you need to find the best sequence, consider dynamic programming as an approach.
Most importantly, before thinking about technical solutions, you should always try to fully understand the problem, and if it does not violate the problem constraints, you can make small adjustments (like adding two endpoints) to make your task easier. Also, remember that sorting can be very helpful when dealing with problems involving intervals or sequences.
The implementation of the solutions in Python, Java, JavaScript, C# and C++ demonstrated that the strategy is consistent across multiple languages. It involved appending new values to the array of cuts, sorting it, and then setting up and filling a DP table using the appropriate formula to calculate minimum cut costs.
In summary, this problem teaches valuable lessons in understanding problem requirements, using dynamic programming, and the importance of sorting in algorithm design. This approach can be applied to solve a myriad of other complex problems in computer science.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.