C# - recursive with memorization - get score


  • 0

    Same recursive idea as others, add in memorization even though the solution without memorization is AC as well. Here we get the best score for player 1 and see if that is enough to win.

    
        public bool PredictTheWinner(int[] nums) 
        {
            Dictionary<Tuple<int,int>, Tuple<int,int>> map = new Dictionary<Tuple<int,int>, Tuple<int,int>>();
            Tuple<int,int> res = Score(nums, 0, nums.Length - 1, map);
            return res.Item1 >= res.Item2;
        }
        
        public Tuple<int,int> Score(int[] nums, int left, int right, Dictionary<Tuple<int,int>, Tuple<int,int>> map)
        {
            if (left == right) return new Tuple<int,int>(nums[left],0);
            Tuple<int,int> key = new Tuple<int,int>(left, right);
            
            if (map.ContainsKey(key)) return map[key];
            
            Tuple<int,int> pickLeft = Score(nums, left + 1, right, map);
            Tuple<int,int> pickRight = Score(nums, left, right - 1, map);
            
            Tuple<int,int> res;
            if (pickLeft.Item2 + nums[left] - pickLeft.Item1 > pickRight.Item2 + nums[right] - pickRight.Item1)
            {
                // left is better pick
                res = new Tuple<int,int>(pickLeft.Item2 + nums[left], pickLeft.Item1);
            }
            else
            {
                // right is better
                res = new Tuple<int,int>(pickRight.Item2 + nums[right], pickRight.Item1); 
            }
            
            map[key] = res;
            return res;
        }
    

Log in to reply
 

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