Problem statement

https://leetcode.com/problems/predict-the-winner/

Solution

The simplest way is to use full recursion with O(2^n) complexity. Smarter ways are to use dp, where dp[i][j] effective score, given numbers from i to j: maximum difference between first and second players. We can evaluate it as dp[i,j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) and in the end we check if dp[0][n-1] is more or equal than 0.

Complexity

Time and space complexity is O(n^2). Space complexity can be reduced to O(n).

Code

class Solution:
    def PredictTheWinner(self, nums):
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 0
            return max(nums[i] - dp(i+1, j), nums[j] - dp(i, j-1))
        
        return dp(0, len(nums) - 1) >= 0