1547. Minimum Cost to Cut a Stick | Leetcode discuss

Here is the link. 

Nov. 16, 2023
1547. Minimum Cost to Cut a Stick

Intuition

I decided to write code to record a path as well in the process of finding minimum cut cost.

Be curious. Be patient. Learn from my curiosity.

Approach

C# LinkedList is used to record the path of cuts for minimum cost.

For example, given example 1, the path can be 3, 5, 1, 4 or 3, 1, 5, 4.

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation:

1. Using cuts order = [1, 3, 4, 5], cost is 20;
2. Using cuts order = [3, 1, 5, 4], cost is 16;
3. Using cuts order = [3, 5, 1, 4], cost is 16.

I set up a test case, and then find the path 3, 1, 5, 4 with minimum cost 16.

public int MinCost(int n, int[] cuts)
{
   var map = new Dictionary<Tuple<int, int>, Tuple<int, LinkedList<int>>>();
   var found= runDFS(cuts, 0, n, map);
   return found.Item1; 

   // minimum cut cost - path detail
   // found.Item2 - a list of int to contain cuts
}

Complexity

• Time complexity:

Let m be the length of the input array cuts.

Time complexity: O(m^3)

The number of states in our DP is the number of possible combinations of (left, right), which is O(m^2)
subproblems. For each subproblem cost(left, right), we need to try all possible cutting positions between new_cuts[left] and new_cuts[right], resulting in an additional factor of mmm. Therefore, the overall time complexity is O(m^3).

• Space complexity:

Space complexity: O(m^2)

We need to store the solutions for all (m^2)
subproblems in memory.

Code

public class Solution {
    /// <summary>
        /// DFS algorithm - memo - efficiency 
        /// Search algorithm 
        /// DFS + memo 
        /// Compared to dynamic programming, I chose to work on a simple DFS solution first. 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="cuts"></param>
        /// <returns></returns>
        public int MinCost(int n, int[] cuts)
        {
            var map = new Dictionary<Tuple<int, int>, Tuple<int, LinkedList<int>>>();
            var found= runDFS(cuts, 0, n, map);
            return found.Item1; 
        }

        /// <summary>
        /// Think about time saving - choose DFS + memo
        /// study code:
        /// https://leetcode.com/problems/minimum-cost-to-cut-a-stick/discuss/971816/C-solution
        /// </summary>
        /// <param name="cuts"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <param name="memo"></param>
        /// <returns></returns>
        Tuple<int, LinkedList<int>> runDFS(int[] cuts, int left, int right, Dictionary<Tuple<int, int>, Tuple<int, LinkedList<int>>> memo)
        {
            if (left >= right)
            {
                return new Tuple<int, LinkedList<int>>(0, null);
            }

            var tuple = new Tuple<int, int>(left, right);

            if (memo.ContainsKey(new Tuple<int, int>(left, right)))
            {
                return memo[tuple];
            }

            var minimumCost = int.MaxValue;
            var list = new LinkedList<int>(); 
            var theCutPosition = -1;
            var leftList = new LinkedList<int>();
            var rightList = new LinkedList<int>(); 

            // apply brute force solution - go through all cut positions one a time
            // try to cut it at the position first, continue on DFS search algorithm
            for (int i = 0; i < cuts.Length; i++)
            {
                var cutPosition = cuts[i];

                if (cutPosition <= left || cutPosition >= right)
                {
                    continue;
                }

                var leftRun = runDFS(cuts, left, cutPosition, memo);
                var rightRun = runDFS(cuts, cutPosition, right, memo);

                var current = right - left + leftRun.Item1 + rightRun.Item1;
                if(current < minimumCost)
                {
                    minimumCost = current;                
                    theCutPosition = cutPosition;
                    leftList = leftRun.Item2;
                    rightList = rightRun.Item2;
                }
            }

            var cost = minimumCost == int.MaxValue ? 0 : minimumCost;

            if (theCutPosition > -1)
            {
                list.AddLast(theCutPosition);
                foreach (var item in leftList)
                {
                    list.AddLast(item);
                }

                foreach (var item in rightList)
                {
                    list.AddLast(item);
                }
            }

            var value = new Tuple<int, LinkedList<int>>(cost, list);

            memo[new Tuple<int, int>(left, right)] = value;

            return memo[tuple];
        }
}