1547. Minimum Cost to Cut a Stick LeetCode Solution

In this guide, you will get 1547. Minimum Cost to Cut a Stick LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Cut a Stick problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Cost to Cut a Stick solution in C++
  4. Minimum Cost to Cut a Stick solution in Java
  5. Minimum Cost to Cut a Stick solution in Python
  6. Additional Resources
1547. Minimum Cost to Cut a Stick LeetCode Solution image

Problem Statement of Minimum Cost to Cut a Stick

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:

See also  787. Cheapest Flights Within K Stops LeetCode Solution

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 <= 106
1 <= cuts.length <= min(n – 1, 100)
1 <= cuts[i] <= n – 1
All the integers in cuts array are distinct.

Complexity Analysis

  • Time Complexity: O(n^3)
  • Space Complexity: O(n^2)

1547. Minimum Cost to Cut a Stick LeetCode Solution in C++

class Solution {
 public:
  int minCost(int n, vector<int>& cuts) {
    cuts.push_back(0);
    cuts.push_back(n);
    ranges::sort(cuts);
    vector<vector<int>> mem(cuts.size(), vector<int>(cuts.size(), INT_MAX));
    return minCost(cuts, 0, cuts.size() - 1, mem);
  }

 private:
  // Returns minCost(cuts[i..j]).
  int minCost(const vector<int>& cuts, int i, int j, vector<vector<int>>& mem) {
    if (j - i <= 1)
      return 0;
    if (mem[i][j] != INT_MAX)
      return mem[i][j];

    for (int k = i + 1; k < j; ++k)
      mem[i][j] = min(mem[i][j], cuts[j] - cuts[i] + minCost(cuts, i, k, mem) +
                                     minCost(cuts, k, j, mem));

    return mem[i][j];
  }
};
/* code provided by PROGIEZ */

1547. Minimum Cost to Cut a Stick LeetCode Solution in Java

class Solution {
  public int minCost(int n, int[] cuts) {
    int[] extendedCuts = new int[cuts.length + 2];
    int[][] mem = new int[extendedCuts.length][extendedCuts.length];
    System.arraycopy(cuts, 0, extendedCuts, 1, cuts.length);
    extendedCuts[0] = 0;
    extendedCuts[extendedCuts.length - 1] = n;
    Arrays.sort(extendedCuts);
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    return minCost(extendedCuts, 0, extendedCuts.length - 1, mem);
  }

  // Returns minCost(cuts[i..j]).
  private int minCost(int[] cuts, int i, int j, int[][] mem) {
    if (j - i <= 1)
      return 0;
    if (mem[i][j] != Integer.MAX_VALUE)
      return mem[i][j];

    for (int k = i + 1; k < j; ++k)
      mem[i][j] = Math.min(mem[i][j],
                           cuts[j] - cuts[i] + minCost(cuts, i, k, mem) + minCost(cuts, k, j, mem));

    return mem[i][j];
  }
}
// code provided by PROGIEZ

1547. Minimum Cost to Cut a Stick LeetCode Solution in Python

class Solution:
  def minCost(self, n: int, cuts: list[int]) -> int:
    A = sorted([0] + cuts + [n])

    @functools.lru_cache(None)
    def dp(i, j):
      if j - i <= 1:
        return 0

      return min(A[j] - A[i] + dp(i, k) + dp(k, j) for k in range(i + 1, j))

    return dp(0, len(A) - 1)
# code by PROGIEZ

Additional Resources

See also  2559. Count Vowel Strings in Ranges LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.