Minimum Cost to Cut a Stick
Leetcode Daily Challenge (28th May, 2023)
Problem Statement:-
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:
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). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.
Link: https://leetcode.com/problems/minimum-cost-to-cut-a-stick/description/
Problem Explanation with examples:-
Example 1
Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:
The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
Example 2
Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.
Constraints
2 <= n <= 10<sup>6</sup>1 <= cuts.length <= min(n - 1, 100)1 <= cuts[i] <= n - 1All the integers in
cutsarray are distinct.
Intuition:-
It's a partition DP problem. We can cut the rod at any point and then solve the subproblems.
For each subproblem, we try to cut the rod at all given cut points and calculate the cost.
We take the minimum of all the costs and return it.
Solution:-
We sort the cuts array and add 0 and n to it. This is because we need to consider the cost of cutting the rod at the ends. Sorting is done to make sure that the cuts are in increasing order.
We define a recursive function solve(i,j) which returns the minimum cost of cutting the rod from i to j.
If i > j, we return 0.
We iterate from i to j and try to cut the rod at each point. We calculate the cost by adding the cost of cutting the rod from i to k-1, k+1 to j, and the cost of cutting the rod at k. Then we take the minimum of the previous minimum and the current cost.
We return the minimum cost.
Finally, we call the solve function with i = 1 and j = len(cuts).
Code:-
JAVA Solution
class Solution {
public int minCost(int n, int[] cuts) {
Arrays.sort(cuts);
int c = cuts.length;
int[] newCuts = new int[c + 2];
newCuts[0] = 0;
System.arraycopy(cuts, 0, newCuts, 1, c);
newCuts[c + 1] = n;
Map<String, Integer> memo = new HashMap<>();
return solve(newCuts, 1, c, memo);
}
private int solve(int[] cuts, int i, int j, Map<String, Integer> memo) {
if (i > j) {
return 0;
}
String key = i + "-" + j;
if (memo.containsKey(key)) {
return memo.get(key);
}
int mn = Integer.MAX_VALUE;
for (int k = i; k <= j; k++) {
mn = Math.min(mn, solve(cuts, i, k - 1, memo) + solve(cuts, k + 1, j, memo) + cuts[j + 1] - cuts[i - 1]);
}
memo.put(key, mn);
return mn;
}
}
Python Solution
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts.sort()
c = len(cuts)
cuts = [0] + cuts + [n]
@cache
def solve(i,j):
if i > j:
return 0
mn = float('inf')
for k in range(i, j+1):
mn = min(mn, solve(i, k-1) + solve(k+1, j) + cuts[j+1] - cuts[i-1])
return mn
return solve(1,c)
Complexity Analysis:-
TIME:-
The time complexity of add method is O(n^3) on average and O(n^4) in the worst case. This is because we still have a nested loop that runs from i to j, resulting in O(n^2) iterations. However, with memoization, we can avoid redundant computations for overlapping subproblems, reducing the overall time complexity to O(n^3) on average. In the worst case, when all subproblems are unique, the time complexity remains O(n^4).
SPACE:-
The space complexity is O(n^2), where n is the number of cuts. This is because we use a HashMap to store the results of previously computed subproblems. The maximum number of unique subproblems is O(n^2) because there can be n choices for the starting index and n choices for the ending index. Hence, the space complexity is O(n^2) due to the additional space required to store the memoization table.