Predict the Winner — LeetCode 486 Python Solution

The problem

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Example

Input

nums = [1,5,2]

Output

false

Explanation

Initially, player 1 can choose between 1 and 2.

Python solution

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            return max(nums[i] - dfs(i + 1, j), nums[j] - dfs(i, j - 1))

        return dfs(0, len(nums) - 1) >= 0

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 486. Predict the Winner is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems