LC.486. Predict the Winner

class Solution1(object):
    def PredictTheWinner(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        self.dict = {}
        return self.DFS(0, len(nums)-1, nums) >= 0

    #当前先手的人比后手的人能多获得多少分, 子问题也是相同的原理，返回的值用当前取得的数减去就行了
    def DFS(self, l, r, nums):
        if l == r:
            return nums[l]
        key = str(l) + "-" + str(r)
        if key not in self.dict:
            # max min问题
            self.dict[key] = max(nums[l] - self.DFS(l+1, r, nums), nums[r] - self.DFS(l, r-1, nums))
        return self.dict[key]

class Solution2(object):
    """
    dp[i][j]表示对于数组数组array[i,j] , 当前先手的人可以比次先手的人最多能多出的分数，那么
    dp[i][j] = nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]
    因为子问题是次选手比当前选手多的分数，所以要用减法
    每个问题都是最优化的解
    核心问题是当前数组下先手的人比后先手的人最多能多出多少分
    """
    def PredictTheWinner(self, nums):
        dp =[[0]*len(nums) for _ in range(len(nums))]
        for j in range(1, len(nums)):
            for i in range(j,-1,-1):
                if i == j :
                    dp[i][j] = nums[i]
                else:
                    dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        return dp[0][-1] >=0