Games

Stone games

5379. Stone Game III

Inspired by lee215, here is my solution.

from functools import lru_cache
class Solution:
    def stoneGameIII(self, A: List[int]) -> str:
        @lru_cache(None)
        def dp(i):
            # beyond the scope, return 0
            if i>=len(A):return 0
            # if only one element left, return this value
            if i==len(A)-1:return A[-1]
            # three actions: pick up 1, pick up 2, pick up 3. 
            # alice_score_of_alice at i = 
            #  max(action_score_of_alice - (action_score_of_bob at i+j+1) for action in 3 cases)
            res = -float('inf')
            for j in range(3):
                if i+j<len(A):
                    this_res = sum(A[i:i+j+1])-dp(i+j+1)
                    res = max(res, this_res)
            return res
        
        if dp(0)>0:return 'Alice'
        elif dp(0)<0:return 'Bob'
        else:return 'Tie'

Some other games problems

Games

1140. Stone Game II

from functools import lru_cache
class Solution:
    def stoneGameII(self, A: List[int]) -> int:
        N = len(A)
        @lru_cache(None)
        def dp(i, M):
            if i+2*M>=N:
                return sum(A[i:])
            res = -float('inf')
            for j in range(2*M):
                this_res = sum(A[i:i+j+1])-dp(i+j+1, max(M,j+1))
                res = max(this_res, res)
            return res
        return (dp(0,1)+sum(A))//2

CUSUM can be used to speed up the computation a little bit.

from functools import lru_cache
class Solution:
    def stoneGameII(self, A: List[int]) -> int:
        N = len(A)
        cusum = list(itertools.accumulate([0]+A))
        @lru_cache(None)
        def dp(i, M):
            if i+2*M>=N:
                return cusum[-1]-cusum[i]
            res = -float('inf')
            for j in range(2*M):
                this_res = cusum[i+j+1]-cusum[i]-dp(i+j+1, max(M,j+1))
                res = max(this_res, res)
            return res
        return (dp(0,1)+sum(A))//2

5447. Stone Game IV

const int M = 1e5+10;
int dp[M];
class Solution {
public:
   unordered_set<int> s;
   vector<int> perfect;
bool helper(int n)
    {
        if (dp[n]!=-1)
        {
            return dp[n]==1;
        }
        if (s.find(n)!=s.end())
        {
            dp[n]=1;
            return true;
        }
          
        for(int i=1;perfect[i]<n;++i)
        {
            if (n-perfect[i]>0 && !helper(n-perfect[i]))
            {
                dp[n]=1;
                return true;
            }   
        }
        dp[n]=0;
        return false;
        
    }
    bool winnerSquareGame(int n) {
         memset(dp, 255, sizeof(dp));
         int i=0;
         while(1)
         {  
             auto kk = i*i;
             if (kk<1e5+10)
             {
                s.insert(kk);
                perfect.push_back(kk);
             }
             else break;
             i++;
         }
        return helper(n);
        
    }
};

A very concise solution from Willam Lin

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<int> dp(n+1);
        for(int i=1; i<=n; ++i) {
            for(int j=1; j*j<=i; ++j)
                dp[i]|=!dp[i-j*j];
        }
        return dp[n];
    }
};