Simple solution using DP


  • 0
    S
    public class Solution {
        int[,] map = new int[100,100];
        public bool PredictTheWinner(int[] nums) {
            int size = nums.Length;
            int ans = dfs(nums, 0, size-1);
            int sum = GetSum(nums, 0, size-1);
            if (ans >= sum - ans) return true;
            return false;
        }
        
        int dfs(int[] nums, int start, int end) {
            if (end < start) return 0;
            if (end == start) return nums[start];
            if (map[start,end] != 0) return map[start,end];
            int sum = GetSum(nums, start, end);
            int subAns1 = dfs(nums, start, end-1), myAns1 = sum - subAns1;
            int subAns2 = dfs(nums, start+1, end), myAns2 = sum - subAns2;
            int ans = myAns1 >= myAns2 ? myAns1 : myAns2;
            map[start, end] = ans;
            return ans;
        }
        
        int GetSum(int[] nums, int start, int end) {
            int ans = 0;
            for (int i=start; i<=end; ++i)
                ans += nums[i];
            return ans;
        }
    }
    
    

Log in to reply
 

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