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.
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 <= 1061 <= cuts.length <= min(n - 1, 100)1 <= cuts[i] <= n - 1cuts array are distinct.This method leverages dynamic programming to find the minimum cost by solving subproblems. We start by sorting the cuts to facilitate an easier partitioning strategy. Then, define a dp table where dp[i][j] represents the minimum cost to perform all the cuts between positions i and j.
Use the recursive relation to compute the minimum cost for each partition (i, j) by considering every possible cut position in that interval. The base case is that if there are no cuts between two positions, the cost is zero.
This C solution sorts the cuts and inserts them along with the stick boundaries into a new array 'newCuts'. The dynamic programming table 'dp' is used to record minimum costs for every subproblem defined by start and end positions in the newCuts array. The cost of each subproblem is solved by iterating over possible cut positions within that range and selecting the smallest achievable cost.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m^3) where m is the number of cuts, due to the nested loops solving subproblems.
Space Complexity: O(m^2) for the dp table storage, where m is the number of cuts.
This approach uses recursive function calls along with a memoization hash table to store the results of subproblem calculations. This reduces repeated calculations and enhances efficiency. Order the cuts, then define a recursive function that selects the appropriate cut division and employs the same function to solve newly formed partitions recursively.
This Python implementation exploits the 'lru_cache' decorator to memoize results of recursive 'cost' function calls, trim down redundant calculations, and obtain a minimum cost sequence quickly.
Java
Time Complexity: O(m^2) with memoization staving off excessive recomputation.
Space Complexity: O(m^2) result-caching leading to rational storage expansion.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m^3) where m is the number of cuts, due to the nested loops solving subproblems. |
| Recursive with Memoization | Time Complexity: O(m^2) with memoization staving off excessive recomputation. |
DP 50. Minimum Cost to Cut the Stick • take U forward • 166,303 views views
Watch 9 more video solutions →Practice Minimum Cost to Cut a Stick with our built-in code editor and test cases.
Practice on FleetCode