Problem statement

https://leetcode.com/problems/stone-game/

Solution 1

Let us dfs(i, j) be the maximum difference Alex can gain if he plays optimally for piles i ... j. There there will be two options: player can take pile i or pile j. Note, that because turn chances, we need to take gain with minus sign, so we have options P[i] - dp(i+1, j) and P[j] - dp(i, j-1) and we choose the maximum one.

Complexity

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

Code

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

Solution 2

We can prove that Alex always wins! The idea is that he always can play in such a way that he get all odd piles or all even piles. On the first move he needs to decide what is bigger and play this strategy.

Complexity

It is just O(1)

Code

class Solution:
    def stoneGame(self, P):
		return True