Why my c# solution gets TLE??


  • 0
    R
    public class Solution {
        public int ShoppingOffers(IList<int> price, IList<IList<int>> special, IList<int> needs)
            {
                var dp = Array.CreateInstance(typeof(long), needs.Select(x => x + 1).ToArray());
                var isVisited = Array.CreateInstance(typeof(bool), needs.Select(x => x + 1).ToArray());
    
                dp.SetValue(0, needs.Select(x => 0).ToArray());
                isVisited.SetValue(true, needs.Select(x => 0).ToArray());
    
                return (int)ShoppingOffersRec(price, special, needs.Select(x => x).ToArray(), dp, isVisited);
            }
    
            long ShoppingOffersRec(IList<int> price, IList<IList<int>> special, int[] pos, Array dp, Array isVisited)
            {
                if ((bool)isVisited.GetValue(pos))
                {
                    return (long)dp.GetValue(pos);
                }
    
                long value = long.MaxValue;
    
                for (int i = 0; i < price.Count; i++)
                {
                    if (pos[i] > 0)
                    {
                        pos[i]--;
                        var resultTemp = ShoppingOffersRec(price, special, pos, dp, isVisited);
                        pos[i]++;
    
                        if (value > resultTemp + price[i])
                        {
                            value = resultTemp + price[i];
                        }
                    }
                }
    
                foreach (var prom in special)
                {
                    if (value <= prom[pos.Length])
                        continue;
                    
                    var canEval = true;
                    for (int i = 0; i < pos.Length; i++)
                    {
                        if (prom[i] > pos[i])
                        {
                            canEval = false;                        
                        }
    
                        pos[i] -= prom[i];
                    }
    
                    if (canEval)
                    {
                        var resultTemp = ShoppingOffersRec(price, special, pos, dp, isVisited);
    
                        if (value > resultTemp + prom[pos.Length])
                        {
                            value = resultTemp + prom[pos.Length];
                        }
                    }
    
                    for (int i = 0; i < pos.Length; i++)
                    {
                        pos[i] += prom[i];
                    }
                }
    
                dp.SetValue(value, pos);
                isVisited.SetValue(true, pos);
    
                return value;
            }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.