1547 Minimum cost to cut a stick - C# - extra requirement - find path as well

1547MinimumCut.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1547_minimum_cut
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Program();
            var minimumCost = test.MinCost(7, new int[] { 1, 3, 4, 5 });
            Debug.Assert(minimumCost == 16);
        }

        /// <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; 

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

        /// <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];
        }
    }
}