Алгоритмический вопрос дня — leetcode 486 — Предсказать победителя (динамическое программирование) — python

【Название Описание】

【Мышление】

Такого рода расчеты, проблема предсказания победителя, распространены. с помощью динамического программирования. Каждый раз вам нужно только подумать, брать ли левое или правое, и сохранить его в двумерном массиве, чтобы взять максимальную разницу между левым и правым. Способ выбора select(i,j) связан только с select(i+1,j) и select(i,j-1), поэтому во избежание повторных вычислений он должен быть восходящим, поэтому рассмотрите возможность рекурсивной реализации .

【Код】

class Solution(object):
    def PredictTheWinner(self, nums):
        n=len(nums)
        dp=[[0]*n for _ in range(n)]
        def selectNumber(l,r):
            if l==r: 
                return nums[l]
            if dp[l][r]>0:
                return dp[l][r]
            dp[l][r]=max(nums[l]-selectNumber(l+1,r),nums[r]- selectNumber(l,r-1))
            return dp[l][r]
        return True if selectNumber(0,n-1)>=0 else False